HDU 2602 Bone Collector（01背包）

最基本的01背包两种实现都要掌握的很熟练！

二维数组实现01背包：

 1 #include <map>
 2 #include <queue>
 3 #include <stack>
 4 #include <math.h>
 5 #include <stdio.h>
 6 #include <string.h>
 7 #include <iostream>
 8 #include <algorithm>
 9 #define LL long long
10 using namespace std;
11 
12 int dp[1010][1010];
13 
14 void run()
15 {
16     int p, n, m;
17     int a[1010], b[1010];
18     scanf("%d", &p);
19     while(p--)
20     {
21         memset(dp, 0, sizeof(dp));
22         scanf("%d%d", &n, &m);
23         for(int i = 1; i <= n; i++)
24             scanf("%d", &a[i]);
25         for(int i = 1; i <= n; i++)
26             scanf("%d", &b[i]);
27         for(int i = 1; i <= n; i++)          ///二维数组实现01背包
28         {
29             for(int j = 0; j <= m; j++)   ///循环从0开始  有体积为0但是有价值的骨头
30             {
31                 if(b[i] <= j && dp[i-1][j] < dp[i-1][j-b[i]]+a[i])
32                     dp[i][j] = dp[i-1][j-b[i]]+a[i];
33                 else
34                     dp[i][j] = dp[i-1][j];
35             }
36         }
37         printf("%d
", dp[n][m]);
38     }
39 }
40 
41 int main(void)
42 {
43     run();
44 
45     return 0;
46 }

Bone Collector

一维数组实现01背包：

 1 #include <map>
 2 #include <queue>
 3 #include <stack>
 4 #include <math.h>
 5 #include <stdio.h>
 6 #include <string.h>
 7 #include <iostream>
 8 #include <algorithm>
 9 #define LL long long
10 using namespace std;
11 
12 int dp[1010];
13 
14 void run()
15 {
16     int p, n, m;
17     int a[1010], b[1010];
18     scanf("%d", &p);
19     while(p--)
20     {
21         memset(dp, 0, sizeof(dp));
22         scanf("%d%d", &n, &m);
23         for(int i = 1; i <= n; i++)
24             scanf("%d", &a[i]);
25         for(int i = 1; i <= n; i++)
26             scanf("%d", &b[i]);
27         for(int i = 1; i <= n; i++)     ///一维数组实现01背包
28         {
29             for(int j = m; j >= b[i]; j--)
30             {
31                 if(dp[j] < dp[j-b[i]]+a[i])
32                     dp[j] = dp[j-b[i]]+a[i];
33             }
34         }
35         printf("%d
", dp[m]);
36     }
37 }
38 
39 int main(void)
40 {
41     run();
42 
43     return 0;
44 }

Bone Collector