题解 | #【模板】01背包#

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct nod {
    int vi;
    int wi;
};
int main(void) {
    int i, j, k, n, m, maxmax, V;
    cin>>n>>V;
    vector<nod> t(n);
    vector<int> dp(V+1, 0); 
    // 装满的话就是dp数组的背包容量值>0，若背包容量<0，则装不满的呢
    fill(dp.begin(), dp.end(), -0xfffffff);
    dp[0] = 0;
    for(i = 0; i < n; i++) scanf("%d %d", &t[i].vi, &t[i].wi); //体积和价值
/*
j顺序递增的，此时的j-t[i].vi是逆序递增，但是j是顺序递增，又dp[0]=0，所以dp[j]的小值先算出来，小容量背包装了物品t[i].wi，不妨设容量是 jk.
随着j递增的，此时j-t[i].vi是逆序递增，当j-t[i].vi=jk时，或者j-t[i].vi是jk的整数倍时，就可以拿了小容量 t[i].wi放入到背包，相当是这件物品被放了两次，重复了，
j顺序递增可以用来求解 完全背包问题，也就是物品可以重复放多次，也就是物品数量无限。
下面的示例分别是j和j-t[i].vi，若j=2时装入了物品t[0]，那么j=4时，还可以继续装入物品t[0]
j     j-t[i].vi
2        0
3        1
4        2


然后来看正常的0-1背包问题的，j逆序递减的，此时的j-t[i].vi是顺序递减，所以dp[j]的右侧大值先算了出来，大容量背包装了物品，不妨设容量是 jb.
随着j递减的，此时的j-t[i].vi顺序递减的，又初始化的小容量都是0或者-inf，大容量装入小容量还是<0或者=0的，不会出现重复装的问题  
下面的示例分别是j和j-t[i].vi，若j=4时装入了物品t[2]，因dp[2]<=0，所以dp[4]基本不变的，而且后续不会重复装入
j     j-t[i].vi
5        3
4        2
3        1
2        0
*/

    for(i = 0; i < n; i++) {
        for(j = V; j >= t[i].vi; j--) {
        // for(j = t[i].vi; j <= V; j++) {
//https://blog.csdn.net/yandaoqiusheng/article/details/84782655
// dp[j]，不放入物体i，背包体积是j能容纳的最大价值；dp[j-t[i].vi] + t[i].wi放入物体i，背包体积是j-t[i].vi能容纳的最大价值
            dp[j] = max(dp[j], dp[j-t[i].vi] + t[i].wi); 
            // cout<<j<<" "<<j-t[i].vi<<endl;
        }
    }
    vector<int>::iterator kk = max_element(dp.begin(), dp.end());
    cout<<kk[0]<<endl;
    if(dp[V] >= 0) cout<<dp[V]<<endl;
    else cout<<0<<endl;
    return 0;
}

/*

j顺序递增的，此时的j-t[i].vi是逆序递增，但是j是顺序递增，又dp[0]=0，所以dp[j]的小值先算出来，小容量背包装了物品t[i].wi，不妨设容量是 jk.

随着j递增的，此时j-t[i].vi是逆序递增，当j-t[i].vi=jk时，或者j-t[i].vi是jk的整数倍时，就可以拿了小容量 t[i].wi放入到背包，相当是这件物品被放了两次，重复了，

j顺序递增可以用来求解 完全背包问题，也就是物品可以重复放多次，也就是物品数量无限。

下面的示例分别是j和j-t[i].vi，若j=2时装入了物品t[0]，那么j=4时，还可以继续装入物品t[0]

j j-t[i].vi

2 0

3 1

4 2

然后来看正常的0-1背包问题的，j逆序递减的，此时的j-t[i].vi是顺序递减，所以dp[j]的右侧大值先算了出来，大容量背包装了物品，不妨设容量是 jb.

随着j递减的，此时的j-t[i].vi顺序递减的，又初始化的小容量都是0或者-inf，大容量装入小容量还是<0或者=0的，不会出现重复装的问题

下面的示例分别是j和j-t[i].vi，若j=4时装入了物品t[2]，因dp[2]<=0，所以dp[4]基本不变的，而且后续不会重复装入

j j-t[i].vi

5 3

4 2

3 1

2 0

*/

for(i = 0; i < n; i++) {

for(j = V; j >= t[i].vi; j--) {

// for(j = t[i].vi; j < V; j++) {

//https://blog.csdn.net/yandaoqiusheng/article/details/84782655

// dp[j]，不放入物体i，背包体积是j能容纳的最大价值；dp[j-t[i].vi] + t[i].wi放入物体i，背包体积是j-t[i].vi能容纳的最大价值

dp[j] = max(dp[j], dp[j-t[i].vi] + t[i].wi);

// cout<<j<<" "<<j-t[i].vi<<endl;

}

}