[学习笔记]0-1背包问题

0-1背包问题：

给定n个物品和一个背包。其中物品i的重量为w_i，价值为v_i，背包容量为c。

问该如何选择放入背包的物品，使得背包中物品价值总和最大？

分析：

问题等价与求集合{x₁,x₂,...,x_n}，其中x_i∈{0，1}。使得：

Σx_iw_i <= c && maxΣv_ix_i

因此可想到递归式：

if (w₁<=j):

　　max(1,j) = v₁

else:

　　max(1,j) = 0

if (w_i<=j):

　　max(i,j) = max{max(i-1,j), max(i-1,j-w_i)+v_i}

else:

　　max(i,j) = max(i-1,j)

(其中max(i，j)表示背包容量为j，可选物品为1，2，...，i)

然后就有以下算法：

 1 #define MAX(a,b) a>b?a:b
 2 
 3 int backpack(int w[], int v[], int n, int c)
 4 {
 5     int max[n+1][c+1];
 6     for (int j = 0; j <= c; j++) 
 7     {
 8         if (j<w[1]) max[1][j] = 0;
 9         else max[1][j] = w[1];
10     }
11     for (int i = 2; i <= n; i++) 
12     {
13         for (int j = 0; j <= c; j++)
14         {
15             if (j < w[i]) max[i][j] = max[i-1][j];
16             else max[i][j] = MAX(max[i-1][j], max[i-1][j-w[i]]+v[i]);
17         }
18     }
19     return max[n][c];
20 }

但是上述方法只是返回了最大价值，要想构造最优解，可以将backpack函数改为返回max数组，然后利用下述函数构造：

 1 int* OptimalSolution(int **m, int w[], int n, int c)
 2 {
 3     int x[n+1];
 4     for (int i = n; i > 1; i--)
 5     {
 6         if (max[i][c]==max[i-1][c]) x[i] = 0;
 7         else
 8         {
 9             x[i] = 1;
10             c-=w[i];
11         }
12     }
13     x[1] = max[1][c]?1:0;
14     return x;
15 }

优化：

（书中有一个优化的算法，暂时不想看。。过两天看看。）

秒客网

[学习笔记]0-1背包问题

相关文章