题解 | #装箱问题#

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(void) {
    // 0-1背包问题的，dp是目标函数，也就是体积是j的最大收益，物体体积已经给出了，要让剩下的体积最小，那么就是使用的体积最大
    // 只需要让收益是体积就可以，若收益最大那么占用的体积最大的
    // 也就是是否选择这件物体，不选择就是dp[i-1][j]，i-1件物品占用j体积的最大收益，选择以后就是dp[i-1][j-num[i]] + num[i]，i-1件物品占用j-num[i]的体积的最大收益
    int i, j, k, m, n, x, y = 0, z = -6, aim, ti;
    cin>>ti>>n;
    vector<int> num(n), dp(ti+1, -0xffffff);
    for(i = 0; i < n; i++) {
        scanf("%d", &num[i]);
    }
    dp[0] = 0;
    for(i = 0; i < n; i++) {
        for(j = ti; j >= num[i]; j--) {
            dp[j] = max(dp[j], dp[j - num[i]] + num[i]);
        }
    }
    vector<int>::iterator it = max_element(dp.begin(), dp.end());
    cout<<ti - it[0]<<endl;
    return 0;
}

/*
    for(i = 0; i < n; i++) {
        for(j = aim; j >= num[i]; j--) {
        // for(j = num[i]; j <= aim; j++) {
            dp[j] = max(dp[j], dp[j - num[i]] + 1);
        }
    }
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
*/

// 0-1背包问题的，dp是目标函数，也就是体积是j的最大收益，物体体积已经给出了，要让剩下的体积最小，那么就是使用的体积最大

// 只需要让收益是体积就可以，若收益最大那么占用的体积最大的

// 也就是是否选择这件物体，不选择就是dp[i-1][j]，i-1件物品占用j体积的最大收益，选择以后就是dp[i-1][j-num[i]] + num[i]，i-1件物品占用j-num[i]的体积的最大收益

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