题解 | #【模板】完全背包#

#include <stdio.h>
#include <limits.h>
int max(int a, int b) {
    return (a > b ? a : b);
}
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    int v[n + 1], w[n + 1], dp[m + 1];
    v[0] = 0, w[0] = 0;
    for (int i = 0; i <= m; i++) {
        dp[i] = 0;
    }
    for (int i = 1; i <= n; i++) {
        
        scanf("%d %d", &v[i], &w[i]);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = v[i]; j <= m; j++) {
            
           
                dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
            

        }
        }
    
    printf("%d\n", dp[m]);
    
        dp[0] = 0;
    
    for (int i = 1; i <= m; i++) {
        dp[i] = INT_MIN;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = v[i]; j <= m; j++) {
           
                dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
            
           
        }
    }
    printf("%d", (dp[m] > 0 ? dp[m] : 0));

    return 0;
}