题解 | #01背包#_牛客博客

解题思路：

普通的01背包，两个dp， $d p_{1}, d p_{2}$ ，令 $dp_{1j}$ 表示在选取物品 $i$ 时，容量为 $j$ 的背包。状态方程是：

dp_{1j} = \max(dp_{1j}, dp_{1j - v_i} + w_i)

令 $d p_{2}$ 表示在选取物品 $i$ 时，容量为 $j$ 的背包，考虑背包 $j$ 正好可以装满的情况。

dp_{2j} = \max(dp_{2j}, dp_{2j-v_i} + w_i),(j-v_i = 0\ or\ dp_{2j-v_i} \neq 0 )

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, V;
    cin>>n>>V;
    vector<int> v(n+1);
    vector<int> w(n+1);
    vector<int> dp(V+1), dp2(V+1);
    int max_w = 0;
    for(int i  = 1; i <= n; ++i){
        cin>>v[i]>>w[i];
    }
    for(int i = 1; i <= n; ++i){
        for(int j = V; j >= v[i]; --j){
            dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
            if(j - v[i] == 0 || dp2[j-v[i]] != 0) dp2[j] = max(dp2[j], dp2[j-v[i]] + w[i]);
        }
    }
    cout<<dp[V]<<endl;
    cout<<dp2[V]<<endl;
    
    return 0;
}