题解 | 【模板】完全背包

#include <iostream>
#include<cstring>
using namespace std;
int dp[1010],dp2[1010];
int v[1010],w[1010];
int main() {
    int n,V;cin>>n>>V;
    for(int i = 1;i<=n;i++){
        cin>>v[i]>>w[i];

    }
    
    // for(int i = 1;i<=n;i++){
    //     for(int j = 1;j<=V;j++){
    //         if(v[i]>j){
    //             dp[i][j] = dp[i-1][j];
    //         }
    //         else{
    //             dp[i][j] = max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
                
    //         }
    //     }
    // }
    for(int i = 1;i<=n;i++){
        for(int j = v[i];j<=V;j++){
            dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    memset(dp2, -0x3f, sizeof dp2);
    dp2[0] = 0;
    for(int i = 1;i<=n;i++){
        for(int j = v[i];j<=V;j++){
            dp2[j] = max(dp2[j],dp2[j-v[i]]+w[i]);
        }
    }
    cout<<dp[V]<<'\n';
    if(dp2[V]<0){
        cout<<0<<'\n';
    }
    else{
        cout<<dp2[V];
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

不知道为什么二维的过不了，希望大佬指出，使用一维可以过。

活动地址https://www.nowcoder.com/discuss/726480854079250432