背景：wa了几次，都是小失误：把i--写成i++之类的，写的时候一定要想到具体用意。还有就是一定要至少写三组测试数据！！！！！！！
学习：模板化写多重背包。
#include#include #include using namespace std; int t,v,n; int c[109],w[109],num[109],F[109]; void zeroonebag(int cost,int weight){ for(int i=v;i >= cost;i--) F[i]=max(F[i],F[i-cost]+weight); } void completebag(int cost,int weight){ for(int i=cost;i <= v;i++) F[i]=max(F[i],F[i-cost]+weight); } void multiplybag(int cost,int weight,int num){ if(cost*num >= v) completebag(cost,weight); else{ int k=1,m=num; while(k < m){ zeroonebag(k*cost,k*weight); m-=k; k*=2; } zeroonebag(m*cost,m*weight); } } int main(void){ scanf("%d",&t); while(t--){ scanf("%d%d",&v,&n); for(int i=0;i < n;i++) scanf("%d%d%d",&c[i],&w[i],&num[i]); memset(F,0,sizeof(F)); for(int i=0;i < n;i++) multiplybag(c[i],w[i],num[i]); printf("%d\n",F[v]); } return 0; }