多重背包问题模版
传送门
问题介于完全背包和01背包之间，不同在于每个物品有确定的数量。
看到这道题的第一思路相比一定是把每种物体分成若干个个体然后01背包跑一遍。但如果总物体数太多的话，显然肯定会无情超时，因此我们要在分割每种物体时应用一点技巧来进行优化。
这里用到的是二进制进行分割优化。
首先要理解一个原理：每个数都可以被拆成若干个以2为底数的不同次幂与另一个数的和，这个显然。在得到这些数后，所有小于等于原数的整数都可以用这些数中的几个数的和进行表示。
举个上课时的栗子：34：可以拆成1.2.4.8.16.3，从1到34每个数都可以用这几个数中的任意几个数之和表示。
完整代码如下：
#include<iostream> #include<cstdio> #include<cmath> using namespace std; int we[1000000],va[1000000],f[1000000]; int main() { int n,w,m=0,x,y,z; cin>>n>>w; for(int i=1;i<=n;i++) { cin>>x>>y>>z; for(int j=1;j<=z;j<<=1) { va[++m]=j*x,we[m]=j*y; z-=j; } if(z) va[++m]=x*z,we[m]=y*z; } for(int i=1;i<=m;++i) for(int j=w;j>=we[i];--j) f[j]=max(f[j],f[j-we[i]]+va[i]); printf("%d",f[w]); return 0; }
转载于:https://www.cnblogs.com/charlesss/p/10291910.html
