0-1 knappack(0-1背包问题)
常见的算法有：
- 枚举
- 贪心
- 动态规划
- 搜索
- 分治和递归
0-1背包是个典型的动态规划算法。
啰嗦一句，动态规划属于运筹学，美国数学家bellman是运筹学的创建者。
0-1背包代码的逻辑如下：
v a l ( i , p ) = v a l ( i − 1 , p ) , p ≥ w i , 0 ≤ p < w i v a l ( i , p ) = m a x ( v a l ( i − 1 , p ) , v a l ( i − 1 , p − w i ) + v i ) , p ≥ w i val(i,p) = val (i -1, p), p \ge w_i, 0 \le p \lt w_i \\ val(i,p) = max (val (i -1, p) ,val(i - 1, p - w_i) + v_i), p \ge w_i val(i,p)=val(i−1,p),p≥wi,0≤p<wival(i,p)=max(val(i−1,p),val(i−1,p−wi)+vi),p≥wi
代码中，需要注意以下几点问题：
- 代码中j为0也是合法的。
- 为什么“val[capacity]”是最后的解？
- 代码逻辑是：先用序号0的物品转满背包，然后从1号物品开始，逐个取出以前装入的物品，并判断新的物品和已装入物品的价值哪个高。因为每种物品的重量不同，所以需要将已装入的物品逐一全部取出，并计算新旧物品的价值大小。
- 0-1背包使用贪心算法可能无法得到最优解的原因是什么？
代码如下：
#include "knapsack.h"#include <stdio.h>#include <string.h>#define MAX_ARRAY_SIZE 1024unsigned int knapsack(unsigned int n, unsigned int*v, unsigned int*w, unsigned int capacity) {unsigned int val[MAX_ARRAY_SIZE] = { 0 };for (int i = 0; i < n; i++) {for (int j = capacity; j >= 0; j--) {int t = val[j - w[i]] + v[i];if (j >= w[i] && val[j] < t) {val[j] = t;}}}return val[capacity];
}int knapsackTest() {unsigned int i, n, c, w[MAX_ARRAY_SIZE],v[MAX_ARRAY_SIZE];int ret = 0;printf("input the number[2-%d]:\r\n", MAX_ARRAY_SIZE);ret = scanf("%d", &n);printf("input the capacity[above 0]:\r\n");ret = scanf("%d", &c);for (int i = 0; i < n; i++) {printf("input weight(remain %d):\r\n",n - i);ret = scanf("%d", &w[i]);}for (int i = 0; i < n; i++) {printf("input value(remain %d):\r\n", n - i);ret = scanf("%d", &v[i]);}unsigned int result = knapsack(n, v, w, c);printf("knapsack:%u\r\n", result);return 0;
}
运行结果：
完整代码地址：https://github.com/satadriver/dataStruct