题解 | 【模板】01背包

#include <cstring>
#include <iostream>
using namespace std;
int v[100100],w[100100],dp[1100][1010];
int main() {
    int V,n;
    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 = V;j>=0;j--){
            dp[i][j] = dp[i-1][j];
            if(j>=v[i]){
                dp[i][j] = max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
            }
            
                
            
        }
    }
    cout<<dp[n][V]<<'\n';
    memset(dp, -1, sizeof dp);
    // for(int i = 1;i<=V;i++){
    //     dp[0][i] = -1;
    // }
    dp[0][0] = 0;
    for(int i = 1;i<=n;i++){
        for(int j = 0;j<=V;j++){
            dp[i][j] = dp[i-1][j];
            if(j>=v[i]&&dp[i-1][j-v[i]]!=-1){
                dp[i][j] = max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
            }
            
        }
    }
    if(dp[n][V]==-1){
        cout<<0<<'\n';
    }
    else{
        cout<<dp[n][V];
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

第一问和第二问稍微不同，第二问需要初始化，将背包容量为0的情况设置价值为0，其它情况设置为最小的Integer型整数，表示不可达状态。后续所有的状态都需要从为0的状态转移过去。状态转移方程为dp[i][j] = max(dp[i-1][j],dp[i][j-v[i]]+w[i]).

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