题目链接：多重背包 II
题意：
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。
数据范围
0 < N ≤ 1000
0 < V ≤ 2000
0 < vi,wi,si ≤ 2000
提示：
本题考查多重背包的二进制优化方法。
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2输出样例：
10思路：
算法 ：动态规划
时间复杂度 ：O(n*m*logs)
完全背包 ：
多重背包 ：
为什么多重背包的方程会比完全背包多出一项？ ：
- 完全背包不需要考虑物品数量，所以上下两个方程都会方程会枚举到 j-kv <= 0 结束，而多重背包第i件物品只有s[i]件，所以下面的方程会多出后面的一项。
能否直接用完全背包的方式优化多重背包 ?
- 考虑已知前n件物品价值的最大值和第n件物品的价值，能否得到前n-1件物品的最大价值？答案是否定的，如果是价值总和我们是可以的，但最大值不可以。
- 这里的前n件物品对应了多重背包的方程，由于多了一项，所以我们不能直接用完全背包的方式优化多重背包。
为什么会超时？ 对于每种物品，如果每次在遍历每种物品和每个体积的时候都枚举一遍物品数量，那么时间复杂度会到O(n^3)，n=1000时，计算量就到了10亿次的级别，而c++一秒只能算1亿次，所以必须考虑优化。
通过二进制的方式对问题进行优化 。
-
对于每个物品如果暴力枚举所有数量会超时，那么考虑将一部分物品分组。我们可以将物品按二进制的方式进行分组：1，2，4，8，，，2^k，C。前k+1项很好理解，分别是2的0~k次方，C是什么？因为我们要通过二进制分组的方式，表达出某个物品的任意数量，那么分组之后的总和也应该等于该物品的数量，C就是该物品的总数量依次减去前k+1项后的值。
-
为什么强调二进制可以表示所有的数字？
因为二进制同样遍历了所有的可能。只要枚举了每件物品二进制分组下的每组物品是否放入背包，那么就相当于枚举了[0,s[i]]，这显然是一种十分高效的枚举手段。 -
这其中也隐含了动态规划的思想，比如如果第1组物品放入背包同时第2组物品也可以放入了背包，那么相当于我们放入了3件物品，如果第1组物品不放入背包而第2组放入背包，就相当于放入了2件物品。后面的每组物品在枚举时都基于前面每组物品是否放入的结果，所以可以节约大量时间。
-
注意数组的范围，需要保证能存下二进制分组后的所有物品
代码：
#include <iostream>
#include <algorithm>
using namespace std;
//注意数组范围，因为我们要存每件物品的数量二进制分组后的总数，
//所以M要取1000*log(2000)=1000*12
const int M=12010;
int n,m;
int v[M],w[M];
int f[2050];
int cnt;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;++i)
{
int x,y,z;
cin>>x>>y>>z;
int k=1;
while(k<=z)
{
cnt++;
v[cnt]=x*k,w[cnt]=y*k;
z-=k;
k*=2;
}
if(z)
{
cnt++;
v[cnt]=x*z,w[cnt]=y*z;
}
}
for(int i=1;i<=cnt;++i)
{
for(int j=m;j>=v[i];--j)
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
cout<<f[m];
return 0;
}
