说说多重背包的循环次序

本文主要是介绍说说多重背包的循环次序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

鉴于多次被体积和次数的循环里外顺序坑，就决定今天跟你好好掰吃掰吃！！！！
1.首先，想说的是，普通的多重背包写法，是相当于每取1次物品就更新一遍体积的值，这就像是01背包一样
要保证当次循环是没更新过的值，所以体积不仅要倒过来，还得要体积在外面，因为
HUA重点！！！！当前层的物品只能用上一层的物品去更新！！！就是这件物品，只能由上一个物品转移过来，
而不是同种物品的不同取法，因为同种物品，只能有一种取法，你总不能拿2次又拿3次吧！！
2.其次，二进制的写法，不多说怎么写了，简单说说为什么这么写。

   for (int k = 1; k <= s; k <<= 1){ve.push_back(k);s -= k;}

每次取2的几次幂个，有的小伙伴不明白为什么要s -= k，比如说我，我刚拿过来这个循环第一想法是
我草！！这尼玛，为什么这s这么牛逼，还能减！！现在回过头来再写这个的时候，只能想当时还是挺脑残的
因为你既然拿了这么多次了，当然就要给人家减下去那么多啊，总不能拿了人家100块钱，人家账户余额
还原封不动吧！还要注意的是跟完全背包不一样的是，体积仍然是倒着的，因为这个看成很多个01背包！不能无限拿！
这个思想就是拆分，因为每种取法，都能有以上几种取法凑出来，所以说当前层的物品需要同种物品的值，
这就相当于你能拿很多次同种物品，仔细体会以上两种写法的区别哦！
3.单调队列，这种写法没什么好说的，因为枚举形式和普通的一样，不是拼凑，所以说不说了！
就酱紫，说实话，俩月之后回来在复习背包问题，发现不像原来想的那么复杂，更不像原来想的那么玄学
每层循环都是有原因的，这就相当于模拟你的决策过程，你想怎么写就怎么写，但要遵守游戏规则。
希望下次回来，我还能犯这些错误！！！！！哈哈哈，加油！！！再次勉励自己一下！！！
也希望不管闲着无聊还是电脑卡顿错点进来看到我写的这些废话，能给更多人带来启发，我想我没有白白反思！
希望全世界的编程爱好者都go go go！
有一道混合背包的题：
https://www.acwing.com/problem/content/7/

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e3 + 7;
int dp[maxn], v, w, s, m;
int main(){int n, m;cin >> n >> m;for (int i = 1; i <= n; i++){cin >> v >> w >> s;if(s == -1){for (int j = m; j >= v; j--)dp[j] = max(dp[j], dp[j - v] + w);}else if(s == 0){for (int j = v; j <= m; j++)dp[j] = max(dp[j], dp[j - v] + w);}else{vector<int>ve;for (int k = 1; k <= s; k <<= 1){ve.push_back(k);s -= k;}if(s)ve.push_back(s);for (auto t : ve){for (int j = m; j >= 0; j--)//这两个循环不能倒过来！if(t*v <= j)dp[j] = max(dp[j], dp[j - t*v] + t*w);}}}printf("%d\n",dp[m]);return 0;
}