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

解题思路：

令 $dp_{1j}$ 表示在选取第 $i$ 个物品时，容量为 $j$ 的背包，由于是完全背包，有状态方程：

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

等同于01背包的状态方程，但是完全背包同一个物品可以放入无数次，可以理解成: $dp_{1j-v_i}$ 是在当前物品 $i$ 放入 $k$ 次的结果，距离当前状态 $dp_{1j}$ 只有放入一次的距离。所以在推导的时候使用的时当前物品前一次放入的状态，而不是上一个物品放入的状态。所以在这里要正向推导。

令 $dp_{2j}$ 表示在选取第 $i$ 个物品时，容量为 $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 (){
    ios::sync_with_stdio(false);
    int n, V;
    cin>>n>>V;
    vector<int> v(n+1), w(n+1);
    vector<int> dp1(V+1), dp2(V+1);
    for(int i = 1; i <= n; ++i){
        cin>>v[i]>>w[i];
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 0; j <= V - v[i]; ++j){
            dp1[j+v[i]] = max(dp1[j+v[i]], dp1[j] + w[i]);
            if(j%v[i] == 0 || dp2[j] != 0) dp2[j+v[i]] = max(dp2[j+v[i]], dp2[j] + w[i]);
        }
    }
    cout<<dp1[V]<<endl;
    cout<<dp2[V]<<endl;

    return 0;
}