NYOJ 49 开心的小明(01背包)

 1 #include<iostream>
 2 #include<memory.h>
 3 using namespace std;
 4 #define max(a,b) a>b?a:b
 5 struct goods{
 6     int v;  //价格
 7     int p;  //重要程度
 8     int w;  //v * p
 9 }a[26];
10 
11 int dp[30001];
12 
13 int main()
14 {
15 //    freopen("in.txt","r",stdin);
16     int t,i,j,N,m;
17     cin>>t;
18     while(t--)
19     {
20         memset(dp,0,sizeof(dp));
21         cin>>N>>m;
22         for(i = 0; i !=m; ++i)
23         {
24             cin>>a[i].v>>a[i].p;
25             a[i].w = a[i].v * a[i].p;
26             for(j = N; j >= a[i].v; --j)
27                 dp[j] = max(dp[j], dp[j - a[i].v] + a[i].w);
28         }
29         cout<<dp[N]<<endl;    
30     }
31     return 0;
32 }