0-1 背包，请问中间结果怎么缓存，结果集怎么获取？

lxyscls

1. #include <string.h>
   
2. #include <stdio.h>
   
3. 
   
4. typedef struct {
   
5.         int v; // value
   
6.         int w; // weight
   
7. } X;
   
8. 
   
9. X x[] = { {20, 2}, {25, 3}, {30, 4}, {40, 5}, {50, 6}};
   
10. 
    
11. #define N 5
    
12. int n = N;
    
13. 
    
14. int bp_size(unsigned bitmap)
    
15. {
    
16.         int i, j = 0;
    
17. 
    
18.         for (i = 0; i < n; i++)
    
19.                 if (bitmap & (1 << i))
    
20.                         ++j;
    
21. 
    
22.         return j;
    
23. }
    
24. 
    
25. int max_r(unsigned bp, int W)
    
26. {
    
27.         int i;
    
28.         int tmp = 0;
    
29.         int max = 0;
    
30. 
    
31.         if (!bp_size(bp))
    
32.                 return 0;
    
33.        
    
34.         for (i = 0; i < n; i++) {
    
35.                 if (bp & (1 << i) && x[i].w <= W) {
    
36.                         tmp = x[i].v + max_r(bp & (~(1 << i)), W - x[i].w);
    
37.                         if (max == 0 || max < tmp) {
    
38.                                 max = tmp;
    
39.                         }
    
40.                 }
    
41.         }
    
42. 
    
43.         return max;
    
44. }
    
45. 
    
46. int main(void)
    
47. {
    
48.         int i;
    
49.         unsigned bp = 0x1f;
    
50. 
    
51.         i = max_r(bp, 10);
    
52. 
    
53.         printf("%d\n", i);
    
54. 
    
55.         return 0;
    
56. }

复制代码

0-1背包，请问中间结果怎么存呢？另外就是结果集怎么存，怎么知道最终结果是哪些组成的？

好像跟一般的动态规划不太一样哦，通常的是i<k<j，左右分开，用["i"][j]矩阵就存下来了，递归就可以了

lxyscls

找到一个 http://www.cnblogs.com/shuaiwhu/archive/2012/05/18/2504175.html，但是不是递归

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. //每件物品的价值和重量
   
5. typedef struct goods_t
   
6. {
   
7.   int weight;
   
8.   int value;
   
9. }goods;
   
10. 
    
11. //动态规划
    
12. int dp(goods* data, const int n, const int weight)
    
13. {
    
14.   int A[n+1][weight+1];
    
15.   int i;
    
16.   //如果i=0或者w=0
    
17.   for (i = 0; i < n+1; i++)
    
18.     A[i][0] = 0;
    
19.   for (i = 0; i < weight+1; i++)
    
20.     A[0][i] = 0;
    
21.   int w;
    
22.   for (i = 1; i <= n; i++)
    
23.   {
    
24.     for (w = 1; w <= weight; w++)
    
25.     {
    
26.       if (data[i-1].weight > w)
    
27.     A[i][w] = A[i-1][w];
    
28.       else
    
29.       {
    
30.     A[i][w] = A[i-1][w] > (data[i-1].value + A[i-1][w-data[i-1].weight]) ? A[i-1][w] : (data[i-1].value + A[i-1][w-data[i-1].weight]);
    
31.       }
    
32.     }
    
33.   }
    
34.   return A[n][weight];
    
35. }
    
36. 
    
37. int main()
    
38. {
    
39.   //输入最大重量
    
40.   int max_weight;
    
41.   scanf("%d", &max_weight);
    
42.   //输入物品件数及其重量和价值
    
43.   int num;
    
44.   scanf("%d", &num);
    
45.   int n = num;
    
46.   goods* data = (goods*)malloc(n*sizeof(goods));
    
47. 
    
48.   goods g;
    
49.   while (num--)
    
50.   {
    
51.     scanf("%d%d", &(g.weight), &(g.value));
    
52.     data[n-num-1] = g;
    
53.   }
    
54.   printf("%d\n", dp(data, n, max_weight));
    
55.   return 0;
    
56. }

复制代码

lxyscls

一L我选择了很蠢的递归方式

二L的应该可以改成递归方式

Susake_

http://www.cnblogs.com/Susake/p/4693241.html
http://www.cnblogs.com/Susake/p/4583500.html

Susake_

有点难，你得明白什么是DP，第i项和第i+1项是有关系的，同理i-1项和i项也是有关系的，....倒推回去第一项(这个逻辑具体怎么写得看你对他的理解了)，记录这个数组，然后再反转...

lxyscls

回复 6# Susake_


    请问什么是DP？

1. #include <string.h>
   
2. #include <stdio.h>
   
3. 
   
4. typedef struct {
   
5.         int v; // value
   
6.         int w; // weight
   
7. } X;
   
8. 
   
9. X x[] = { {20, 2}, {25, 3}, {30, 4}, {40, 5}, {50, 6}};
   
10. 
    
11. #define N 5
    
12. #define W 10
    
13. 
    
14. int r[N+1][W+1]; // choice record
    
15. int m[N+1][W+1]; // middle result
    
16. 
    
17. void max_r(int n, int w)
    
18. {
    
19.         if (m[n][w] != -1)
    
20.                 return;
    
21. 
    
22.         if (n == 0 || w == 0) {
    
23.                 m[n][w] = 0;
    
24.                 return;
    
25.         }
    
26. 
    
27.         if (x[n-1].w > w) {
    
28.                 max_r(n-1, w);
    
29.                 m[n][w] = m[n-1][w];
    
30.                 r[n][w] = n - 1;
    
31.         } else {
    
32.                 max_r(n-1, w);
    
33.                 max_r(n-1, w - x[n-1].w);
    
34. 
    
35.                 if (m[n-1][w] > x[n-1].v + m[n-1][w-x[n-1].w]) {
    
36.                         m[n][w] = m[n-1][w];
    
37.                         r[n][w] = n - 1;
    
38.                 } else {
    
39.                         m[n][w] = x[n-1].v + m[n-1][w-x[n-1].w];
    
40.                         r[n][w] = n;
    
41.                 }
    
42.         }
    
43. }
    
44. 
    
45. void print_r(int n, int w)
    
46. {
    
47.         if (n == 0 || w == 0)
    
48.                 return;
    
49. 
    
50.         if (r[n][w] == n) {
    
51.                 printf("%d\n", n - 1);
    
52.                 print_r(n-1, w-x[n-1].w);
    
53.         } else {
    
54.                 print_r(n-1, w);
    
55.         }
    
56. }
    
57. 
    
58. int main(void)
    
59. {
    
60.         memset(m, -1, sizeof(m));
    
61.         memset(r, -1, sizeof(r));
    
62. 
    
63.         max_r(N, W);
    
64. 
    
65.         printf("%d\n", m[N][W]);
    
66. 
    
67.         print_r(N, W);
    
68. 
    
69.         return 0;
    
70. }

复制代码

lxyscls

回复 3# __BlueGuy_


    递归可以缓存，见7L
    这个问题奇葩就奇葩在，中间结果需要存储在一个 （n + 1 * w + 1）的矩阵里面，中间选择也存储在这样一个矩阵里面
    之前接触的问题，都是存储在一个（n+1 * n+1）的矩阵里面，打死都想不出

何必抱怨

DP是动态规划

lxyscls

我晕，缩写害死人啊

我后面用的递归应该就是动态规划了吧