[再做01背包] POJ 3624 Charm Bracelet

 1 //#define LOCAL
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 const int maxn = 13000 + 10;
 8 int dp[maxn];
 9 int cost[3500], weight[3500];
10 
11 int main(void)
12 {
13     #ifdef LOCAL
14         freopen("3624in.txt", "r", stdin);
15     #endif
16 
17     int n, v;
18     int i;
19     scanf("%d%d", &n, &v);
20     memset(dp, 0, sizeof(dp));
21     for(i = 1; i <= n; ++i)
22         scanf("%d%d", &cost[i], &weight[i]);
23 
24     int j;
25     for(i = 1; i <= n; ++i)
26         for(j = v; j >= cost[i]; --j)
27         {
28             dp[j] = max(dp[j], dp[j-cost[i]] + weight[i]);
29         }
30 
31     printf("%d\n", dp[v]);
32     return 0;
33 }