[niuke.com] DP30 [template] 01 Backpack

The output of the first line is typical 0-1 knapsack problem , And the second line is that the volume is required to be fixed with the maximum value , Therefore, we need to dp2 Initialize to int The minimum value that a type can express , And will dp2[ 0 ] The assignment is 0.

#include<iostream>
#include<cstdio>
#include<climits>

using namespace std;

const int N = 1000 + 10;

int w[N], v[N], dp1[N], dp2[N];

int main(){
    
    int n, m;
    while(scanf("%d%d", &n, &m) != EOF){
    
        for(int i = 0; i < n; i++) scanf("%d%d", &w[i], &v[i]);
        fill(dp2, dp2 + m + 1, -INT_MAX);
        dp2[0] = 0;
        for(int i = 0; i < n; i++){
    
            for(int j = m; j >= w[i]; j--){
    
                dp1[j] = max(dp1[j], dp1[j - w[i]] + v[i]);
                dp2[j] = max(dp2[j], dp2[j - w[i]] + v[i]);
            }
        }
        printf("%d\n", dp1[m]);
        if(dp2[m] < 0) printf("0\n");
        else printf("%d\n", dp2[m]);
    }
    return 0;
}