poj2063_01背包+技巧

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cstdlib>
 6 #include <cmath>
 7 #include <set>
 8 #include <map>
 9 #include <vector>
10 using namespace std;
11 
12 int max(int a, int b)
13 {
14     return a > b ? a : b;
15 }
16 int dp[100000];
17 int main()
18 {
19     int t, i, j, k, n, m, d, v[20], p[20];
20     scanf("%d", &t);
21     while(t--)
22     {
23         scanf("%d %d %d", &n, &m, &d);
24         for(i = 1; i <= d; i++){
25             scanf("%d %d", v + i, p + i);
26             v[i] /= 1000;　　//题目有说存的钱一定是千的倍数
27         }        
28         for(i = 1; i <= m; i++)
29         {
30             int s = n / 1000;
31             memset(dp, 0, sizeof(dp));
32             for(j = 1; j <= d; j++)
33             {
34                 for(k = v[j]; k <= s; k++)
35                     dp[k] = max(dp[k], dp[k - v[j]] + p[j]);
36             }
37             n += dp[s];
38             //cout << n << endl;
39         }        
40         printf("%d
", n);
41     }    
42     return 0;
43 }