多重背包

多重背包和01背包类似，基本上只是多了一个循环

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 using namespace std;
 5 int dp[120];
 6 int value[1100];  //花费
 7 int popular[1100]; //受欢迎程度
 8 int num[1100]; //每种物品的件数
 9 int main()
10 {
11     int n,m;
12     cin>>m>>n;
13     for(int i=1;i<=n;i++)
14     {
15         cin>>value[i]>>popular[i]>>num[i];
16     }
17     for(int i=1;i<=n;i++)
18         for(int k=1;k<=num[i];k++)        
19             for(int j=m;j>=value[i];j--)
20                 dp[j]=max(dp[j],dp[j-value[i]]+popular[i]);
21     cout<<dp[m]<<endl;
22     return 0;
23 }