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

#include <iostream>
#include<bits/stdc++.h>
//与01背包区别不大，就下面两处，恰好装满时的解决思路也是和01背包一模一样
#include <vector>
using namespace std;

int main() {
    int n,V;
    cin>>n>>V;
    vector<int >v(n+1,0);
    vector<int>w(n+1,0);
    vector<int>dp1(V+1,0);
    vector<int>dp2(V+1,-11111111);
    for(int i=1;i<=n;i++){
        cin>>v[i]>>w[i];
    }
    dp2[0]=0;
    for(int i=1;i<=n;i++){
       for(int j=v[i];j<=V;j++){//完全背包与01背包的唯一区别：01-> for(int j=V;j>=v[i];j--)
            dp1[j]=max(dp1[j],dp1[j-v[i]]+w[i]);
        }
    }
    cout<<dp1[V]<<endl;
    for(int i=1;i<=n;i++){
        for(int j=v[i];j<=V;j++){//完全背包与01背包的唯一区别：01-> for(int j=V;j>=v[i];j--)
            dp2[j]=max(dp2[j],dp2[j-v[i]]+w[i]);
        }
    }
    if(dp2[V]>0)
    cout<<dp2[V]<<endl;
    else
     cout<<"0";
}
// 64 位输出请用 printf("%lld")