#include<iostream>#include<cstdio>using namespace std;struct rice{int p;int h;}rice[505];int max(int a,int b) {return a>b?a:b;}int main(){int t,n,m,p,h,c,i,j,f[101],k;cin>>t;while(t–){scanf("%d%d",&n,&m);k=0;for(i=0;i<m;i++){scanf("%d%d%d",&p,&h,&c);j=1;while(j<=c){rice[k].p = j*p;rice[k++].h=j*h;c-=j;j=j*2;}rice[k].p = c*p;rice[k++].h = c*h;}for(i=0;i<=n;i++)f[i]=0;for(i=0;i<k;i++)for(j=n;j>=rice[i].p;j–)f[j]=max(f[j],f[j-rice[i].p]+rice[i].h);cout<<f[n]<<endl;}return 0;}
原来这就叫多重背包，，用二进制把它简化放入rice[]就是01了
状态：f[j]:j是所花的经费
状态转移：f[j]=max{f[j],f[j-rice[i].p]+rice[i].h}
人言未必皆真，听言只听三分。
