题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2191
多重背包：
1 #include <iostream> 2 #include<algorithm> 3 #include<cstring> 4 using namespace std; 5 int t,n,m; 6 int v[1110],w[1110],num[1110]; 7 int dp[1110]; 8 int main() 9 { 10 cin>>t; 11 while(t--) 12 { 13 int ans=0; 14 cin>>n>>m; 15 for(int i=0;i<m;i++) 16 cin>>v[i]>>w[i]>>num[i]; 17 memset(dp,0,sizeof(dp)); 18 for(int i=0;i<m;i++) 19 { 20 int nu=num[i]; 21 for(int k=1;nu>0;k*=2) //二进制划分 22 { 23 int tmp=min(k,nu); 24 for(int j=n;j>=tmp*v[i];j--) 25 dp[j]=max(dp[j],dp[j-tmp*v[i]]+tmp*w[i]); 26 nu-=tmp; 27 } 28 } 29 for(int i=0;i<=n;i++) 30 ans=max(ans,dp[i]); 31 cout<<ans<<endl; 32 } 33 }