题解 | #【模板】01背包#

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int main(){
    int i,j,n,c;
    int ans1,ans2 = 0;
    cin >> n >> c;
    int w[1001],v[1001];
    for(i = 1; i <= n; i++) cin >> w[i] >> v[i];
    int V[1001][1001];
    int Vi[1001][1001];
    for (i = 0; i <= n ; ++i) {
        V[i][0] = 0;
    }
    for (j = 0; j <= c; ++j) {
        V[0][j] = 0;
    }

    for (i = 1; i <= n; ++i) {
        for (j = 1; j <= c; ++j) {
            if (j < w[i]){
                V[i][j] = V[i - 1][j];
            } else{
                V[i][j] = max(V[i - 1][j],V[i - 1][j - w[i]] + v[i]);
            }
        }
    }

    cout << V[n][c] << endl;
    for (i = 0; i <= n; i++) {
        for(j = 0;j<= c;j++){
            Vi[i][j] = -9999;
        }
    }
    Vi[0][0]=0;
    for (i = 1; i <= n; i++) {
        for (j = 0; j <= c; j++) {
            if (w[i] > j) {
                Vi[i][j] = Vi[i - 1][j];
            } else {
                Vi[i][j] = max(Vi[i - 1][j],Vi[i - 1][j - w[i]] + v[i]);
            }
        }
    }
    if(Vi[n][c]<0){
        Vi[n][c]=0;
    }
    cout<<Vi[n][c];


}