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

解题思路：

• 令$d{p}_{1j}dp\_\{1j\}$表示在选取第$ii$个物品时，容量为$jj$的背包，由于是完全背包，有状态方程：

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

• 令$d{p}_{2j}dp\_\{2j\}$表示在选取第$ii$个物品时，容量为$jj$的背包，和上一个区别在于要带条件，即正好装满。有方程：

#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;
}