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

背包问题和刚刚好背包问题的区别

初值不同，普通完全背包问题dp[i] = 0 而对于刚刚好背包问题dp[i] = 0x80000000(int最小值) 没装满视为价值为int最小值 而dp[0] = 0

#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
int main(){
    int M,N;
    while(cin>>N>>M){
        int v[N];int w[N];
        for(int i=0;i<N;i++){
            cin>>w[i]>>v[i];
        }
        int dp[M+1] ;
        memset(&dp, 0, sizeof(dp));
        for(int i=0;i<N;i++){
            for(int j=w[i];j<=M;j++){
                dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
            }
        }
//         cout<<*max_element(dp,dp+M+1)<<"\n";
        cout<<dp[M]<<"\n";
        for(int i=0;i<M+1;i++){
            dp[i] = 0x80000000;
        }
         dp[0] = 0;
        for(int i=0;i<N;i++){
            for(int j=w[i];j<=M;j++){
                dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
            }
        }
        cout<<((dp[M]<0)?0:dp[M])<<"\n";
    }
}