1269：【例9.13】庆功会 多重背包

1. 由于此题每件物品可以选给定的某一数量件，这就是多重背包的知识，有点像P1616 疯狂的采药 完全背包中的01背包思路的解法，毕竟我觉得多重背包就是特殊的完全背包，因为虽然每件物品可以多选，但是多重背包选取的件数k是根据题目给出的范围选取的，完全背包通过当前容量最多装取的个数选取的；
2. 复习一下：

• 01背包是每种物品只有一件，复习一维背包，戳这里P1048 采药 java 01背包；
• 完全背包就是没件物品随便选，复习完全背包，戳这里P1616 疯狂的采药 完全背包；

3. 总结：在一维dp中，需要记住01背包的j是逆序遍历的，因为后面的处理需要用上前面的，不能造成覆盖；完全背包的一维dp的j是从正序遍历的，因为当前行的dp值依赖于当前j减去一个weight值的dp值；多重背包和01背包有点相似，只不过增加了一层循环k，也就是当前物品可以选取多件，j也是逆序遍历的，因为就是01背包的打表思想；

这个代码没有进行优化，其实有多重背包的二进制优化

#include "bits/stdc++.h"

using namespace std;
typedef long long ll;
int dp[6010];
int value[510];//价值
int weight[510];//价格
int s[510];//每个物品的个数
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> weight[i] >> value[i] >> s[i];
    }
    //类似于01背包
    for (int i = 1; i <= n; ++i) {
        //01逆序，完全背包正序
        for (int j = m; j >= 0; j--) {
            for (int k = 0; k <= s[i]; ++k) {
                if (k * weight[i] <= j)
                    dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i]);
            }
        }
    }
    cout << dp[m];
    return 0;
}

参考博客：多重背包问题（二进制优化），参考视频：多重背包 二进制优化；

其实就是拆分的思想，把某一件物品的总件数，利用二进制去拆分成每件物品的数量均为1，然后为相应的价值的新物品；最后就是一共拆分出cnt件新物品，每件物品的数量都为1，对应着其相应的价值。
需要注意数组创建的空间，因为拆分出来更大件，不能在按照题上的；

#include "bits/stdc++.h"

using namespace std;

//需要增大数组容量，因为会拆分出来更多件商品
int dp[60100];
int value[5100];//价值
int weight[5100];//价格

int main() {
    int n, m;
    cin >> n >> m;
    //预处理，二进制优化
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        int w, v, s;//分别代表当前物品的价格、价值、件数
        cin >> w >> v >> s;
        //依次：1,2,4,8，...至到最后一个数为剩余的件数
        for (int j = 1; j <= s; j <<= 1) {
            cnt++;
            weight[cnt] = w * j;
            value[cnt] = v * j;
            s -= j;
        }
        //最后为剩余的件数
        if (s > 0) {
            cnt++;
            weight[cnt] = w * s;
            value[cnt] = v * s;
        }
    }
    //经过上面操作，拆分出来了cnt件物品
    for (int i = 1; i <= cnt; ++i) {
        //01逆序，完全背包正序
        for (int j = m; j >= weight[i]; j--) {
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    cout << dp[m];
    return 0;
}