分析:多重背包问题。这里直接转换为01背包,,为使用二进制。
#include<iostream>using namespace std;int price[101];int weight[101];int number[101];int dp[101];int main(){int C,n,m;int i,j,k;cin>>C;while(C–){cin>>n>>m;for(i=0;i<m;i++){cin>>price[i]>>weight[i]>>number[i];}memset(dp,0,sizeof(dp));//多重背包,未用二进制优化,转换为0-1背包for(i=0;i<m;i++)for(j=1;j<=number[i];j++)for(k=n;k>=price[i];k–)if(dp[k]<dp[k-price[i]]+weight[i])dp[k]=dp[k-price[i]]+weight[i];cout<<dp[n]<<endl;}return 0;}
含泪播种的人一定能含笑收获。