問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3624思路:
典型的01背包問題，動態規劃，參考背包九講
注意需要使用滾動數組，否則MLE
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_N 3403
5 #define MAX_M 12881
6 #define max(a,b) ((a)>(b) ? (a) : (b))
7 int n, m;
8 /* MLE: int table[MAX_N][MAX_M]; */
9 int table[MAX_M];
10 int weight[MAX_N], rate[MAX_N];
11
12 void
13 dp()
14 {
15 int i, j;
16 memset(table, 0, sizeof(table));
17 for(i=1; i<=n; i++)
18 for(j=m; j>=weight[i]; j--) /* Attention: descent order */
19 table[j] = max(table[j], table[j-weight[i]]+rate[i]);
20 }
21
22 int
23 main(int argc, char **argv)
24 {
25 int i;
26 while(scanf("%d %d", &n, &m)!=EOF) {
27 for(i=1; i<=n; i++)
28 scanf("%d %d", weight+i, rate+i);
29 dp();
30 printf("%d\n", table[m]);
31 }
32 }