# 由DAG到背包问题——记忆化搜索和递推两种解法

2018/08/08 23:12

1、记忆化搜索

1 #include<stdio.h>
2 #include<iostream>
3 #include<cstring>
4 #include<algorithm>
5 using namespace std;
6
7 const int INF = 0x3f3f3f3f;
8 const int maxn = 100 + 10;
9 const int maxc = 10000 + 10;
10 int n,V[maxn],W[maxn],C;
11 int d[maxc];        //d[i]表示总体积恰好为i时的最大重量
12
13 int dp(int s)
14 {
15     int& ans = d[s];
16     if (ans != -1)  return ans;
17     ans = - INF;
18     for (int i = 0; i < n; i++)
19     {
20         if (s >= V[i])  ans = max(ans, dp(s - V[i]) + W[i]);
21     }
22     return ans;
23 }
24 void slove()
25 {
26     memset(d, -1, sizeof(d));
27     d[0] = 0;
28     int res = -1;
29     for (int i = 0; i <= C; i++)
30         res = max(res, dp(i));
31     printf("%d\n", res);
32 }
33
34 int main()
35 {
36     while (scanf("%d",&n) == 1 && n)
37     {
38         scanf("%d", &C);
39         for (int i = 0; i < n; i++)
40             scanf("%d%d", &V[i], &W[i]);
41
42         slove();
43     }
44     return 0;
45 }

2、递推式

1 void slove()
2 {
3     fill(d, d + n, -INF);
4     d[0] = 0;
5     int res = -1;
6     for (int i = 0; i <= C; i++)        //容量的循环顺序只能是从小到大
7     {
8         for (int j = 0; j < n; j++)
9         {
10             if(i >= V[j])  d[i] = max(d[i], d[i - V[j]] + W[j]);
11         }
12         res = max(res, d[i]);
13     }
14     printf("%d\n", res);
15 }

3、两者比较

0
0 收藏

0 评论
0 收藏
0