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

这道题在弄懂01背包问题后基本没有难度。
基本思路与01背包问题相同。唯一不同的是，题目中的物品可以重复加入，而01背包问题中要避免物品重复加入。
在01背包问题中，避免重复添加一件物品是通过逆序遍历来实现的，而在本题中要包含重复添加一件物品的情况，只需将逆袭改为正序遍历即可。

附01背包问题题解

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int n, v;
    cin >> n >> v;
    vector<int> pa(n);
    vector<int> va(n);
    for(int i = 0;i < n;i++){
        cin >> va.at(i) >> pa.at(i);
    }
    vector<int> res(v + 1, 0);
    vector<int> cres(v + 1, -99999);
    cres.at(0) = 0;
    for(int i = 0;i < n;i++){
        for(int j = va.at(i);j <= v;j++){
            res.at(j) = max(res.at(j), res.at(j - va.at(i)) + pa.at(i));
            cres.at(j) = max(cres.at(j), cres.at(j - va.at(i)) + pa.at(i));
        }
    }
    int max = res.at(v);
    int cmax = cres.at(v) > 0 ? cres.at(v) : 0;
    cout << max << endl << cmax;
    return 0;
}