什么是 0-1 背包问题

假设，有一堆种类各不相同的宝石，还有一个背包，这个背包承重能力有限为 17。怎么让背包中装的宝石最值钱。装到包中用 1 表示，不装到包中用 0 表示，所以解是由 0，1 组成的序列。简称 0-1 背包问题。
下表是宝石的重量和价值

如何求解

从问题可以看出，已知数据是每个宝石的重量和价值，背包的承重 WWW。
用 wiw_iwi​ 表示第 iii 个宝石的重量，viv_ivi​ 表示第 iii 个宝石的价值，装入背包的宝石的最大价值可表示为：
max∑i=1nviximax\sum_{i=1}^nv_ix_i maxi=1∑n​vi​xi​
且满足如下约束条件
∑i=1nwixi≤W，xi∈{0,1}\sum_{i=1}^nw_ix_i \le W，x_i \in\{0,1\} i=1∑n​wi​xi​≤W，xi​∈{0,1}
如何求得满足约束条件的最大值呢？
分析一下，假如 xnx_nxn​ 要装入包中，那么 {xn−1,...,x1}\{x_{n-1},...,x_1\}{xn−1​,...,x1​} 肯定是 W−wnW - w_nW−wn​ 的解，假如 xnx_nxn​ 不装入包中，那么 {xn−1,...,x1}\{x_{n-1},...,x_1\}{xn−1​,...,x1​} 肯定是 WWW 的解。

通过上面的分析我们可以得出，如下结论：
c[i,w]={0,i=0或w=0c[i−1,w],wi>wmax{c[i−1,w−wi]+vi,c[i−1,w]},i>0且wi≤wc[i,w]=\left\{ \begin{aligned} &0&,i=0 或 w=0 \\ &c[i-1,w]&,w_i>w\\ &max\{c[i-1,w-w_i]+v_i,c[i-1,w]\}&,i>0 且w_i \le w \end{aligned} \right. c[i,w]=⎩⎪⎨⎪⎧​​0c[i−1,w]max{c[i−1,w−wi​]+vi​,c[i−1,w]}​,i=0或w=0,wi​>w,i>0且wi​≤w​
其中 c[i,w]c[i,w]c[i,w] 表示背包容量为 www 时 iii 个物品导致的最优解的总价值。我们要求的目标是 c[n,W]c[n,W]c[n,W]
求解思路是找出 www 从 [0,W][0,W][0,W] 的所有解，然后从中找出最优解。
这里用到的算法策略是动态规划法。

对应的求解程序

#include 
#include 
/* 
n 物品数量
W 背包容量
Weights 物品重量
Values 物品价值
求出 c[i,w] 的所有值,其中 1<= i <=n,1<=w<=W
*/
int **KnapsackDP(int n, int W, int *Weights, float *Values)
{int i, w;int **c = (int **)calloc(n + 1, sizeof(int *));for (i = 0; i <= n; i++)c[i] = (int *)calloc(W + 1, sizeof(int));//求解for (i = 1; i <= n; i++){for (w = 1; w <= W; w++){if (Weights[i - 1] <= w){if (Values[i - 1] + c[i - 1][w - Weights[i - 1]] > c[i - 1][w]){c[i][w] = Values[i - 1] + c[i - 1][w - Weights[i - 1]];}else{c[i][w] = c[i - 1][w];}}else{c[i][w] = c[i - 1][w];}}}return c;
}
void OutputKnapsackDP(int n, int W, int *Weights, float *Values, int **c)
{int x[n];int i;for (i = n; i > 1; i--){if (c[i][W] == c[i - 1][W])x[i - 1] = 0;else{x[i - 1] = 1;W = W - Weights[i - 1];}}if (c[1][W] == 0)x[0] = 0;elsex[1] = 1;for (i = 0; i < n; i++){if (x[i] == 1){printf("Weigh: %d,Value: %f\n", Weights[i], Values[i]);}}
}int main(void)
{int n = 5, W = 17;int Weights[] = {3, 4, 7, 8, 9};float Values[] = {4, 5, 10, 11, 13};int **c = KnapsackDP(n, W, Weights, Values);OutputKnapsackDP(n, W, Weights, Values, c);
}