HDU 2191 HDU 2191 悼念512汶川大地震遇难同胞――珍惜现在，感恩生活 (01背包入门)

 1 /*************************************
 2 
 3   01背包入门题
 4   把每袋大米做01背包就可以了。
 5   http://acm.hdu.edu.cn/showproblem.php?pid=2191
 6   
 7 *************************************/
 8 
 9 #include<iostream>
10 #include<cstring>
11 #include<algorithm>
12 using namespace std;
13 
14 const int mx=111;
15 int dp[mx],p[mx];
16 int h[mx],c[mx];
17 
18 int main()
19 {
20     int n,m,i,j,t;
21     cin>>t;
22     while (t--)
23     {
24         cin>>n>>m;
25         for (i=0;i<m;i++) cin>>p[i]>>h[i]>>c[i];
26         memset(dp,0,sizeof(dp));
27 
28         for (i=0;i<m;i++)   ///01背包模板
29         {
30             while (c[i]--)  ///把每袋大米做01背包就可以了。
31             {
32                 for (j=n;j>=p[i];j--)
33                 dp[j]=max(dp[j],dp[j-p[i]]+h[i]);
34             }
35         }
36         cout<<dp[n]<<endl;
37     }
38 
39 }