有一个容量为\(M\)的背包，有\(N\)种物品，每种物品有其对应的体积\(W_i\)，价值\(V_i\),数量\(S_i\). 输入格式： 第一行：\(M\),\(N\) 第\(2\)至第\(N+1\)行，每行\(3\)个正整数，分别为 体积\(W_i\)，价值\(V_i\),数量\(S_i\)。 输出格式： 一行：最大价值。
直接暴力：
\(dp_i=max(dp_{i-W_i}*S+V_i * S)\)
显然复杂度爆炸，那该怎么优化呢？
方法：将每个物品拆成\({2^0,2^1,...2^p,S_i-2^p}\)满足\(0<S_i-2^p<2^{p+1}\)原理:\(2^0,2^1,2^2...2^{k-1}\)可以凑成\(2^k-1\)之间的所有整数。 设$a_i=S_i - \sum_{i=0}^p 2^i $ 由于\(p\)最大，所以\(2^0,2^1...2^p\)可以表示出\([0,a_i]\)间的所有整数。 由于\(2^0,2^1...2^p\)可以表示出\(a_i~a_i+2^p-1\)以内的所有整数，又因为\(a_i=S_i + 1-2……{p+1}\), 所以\(2^0,2^1...2^p\)可以凑成\(a_i~S_i\)之间 的所有整数。 故成立。转载于:https://www.cnblogs.com/defense/p/11480908.html
相关资源：贪心算法解多重背包代码