背包问题是一个组合优化问题，题目描述如下：
给定一个固定大小、容量为C的背包，以及一组有价值和重量的物品，找出一个最佳的解决方案，使得装入背包的物品重量小于W，且价值最大。
通俗的描述就是：
你有一个书包，还有一堆物品摆在你的面前，手机、电脑、平板、砖头，而你的书包只能装5斤东西，装哪些东西最赚？
理解了题目意思我们再来看一个输入输出例子
输入
weight:[2,3,4,5,9] //重量
values:[3,4,5,8,10] //价值
C:20 //背包容量
| 物品 | 价值 | 重量 |
|---|---|---|
| 0 | 3 | 2 |
| 1 | 4 | 3 |
| 2 | 5 | 4 |
| 3 | 8 | 5 |
| 4 | 10 | 9 |
输出
选取物品0、2、3、4，总价值为3+5+8+10 = 26
maxValue:26
我们假设公式B(k,c)表示有k个物品，容量为C时的最大价值
问题便转为求B(4,20)的值
- 当k指向第4个物品时，重量为9，明显小于背包容量C，所以我们可以将物品4装入背包，故
B(4,20) = B(3,20-9)+10 = B(3,11)+10
别忘了我们追求的是最大价值，如果把物品4装进去那容量就变小了，装不进其他物品，所以对于小于背包容量的物品，我们有两个选择
- 装进去
B(4,20) = B(3,20-9)+10 = B(3,11)+10 - 不装
B(4,20) = B(3,20)
如果物品4的重量为100，明显超出背包容量时，那B(4,20)等于多少呢？
既然装不下，那我们就忽略掉物品4，让k指针指向上一个物品，容量不变
B(4,20) = B(3,20)
通过以上分析我们可以得出B(k,c)的递归公式
我们来分析B(4,20)的执行过程，可以发现实际上这个公式是二叉树的形式
看懂了上图，这题可以使用递归方法解决，但更好地解法是使用动态规划。
动态规划是一种将复杂问题分解成更小的子问题来解决的优化技术
算法如下：
function kanpSack(capacity, weights, values, n) {
var a,b,KS = []
//首先，初始化用于寻找解决方案的矩阵KS[n+1][capacity+1]
for (var i = 0; i <= n; i++) {
KS[i] = [];
}
for (var i = 0; i <= n; i++) {
for (var w = 0; w <= capacity; w++) {
if (i === 0 || w === 0) {
//让第一行和第一列为0，因为第一行和第一列表示容量为0或没有物品可装
KS[i][w] = 0;
} else if (weights[i - 1] > w) {
KS[i][w] = KS[i - 1][w]; //当前物品重量大于当前容量
} else {
//当前物品重量小于当前容量，有两个选择，装或者不装，取价值最大的
a = KS[i - 1][w - weights[i - 1]] + values[i - 1]; //装入这个物品后的总价值
b = KS[i - 1][w]; //不装
KS[i][w] = a > b ? a : b;
}
}
}
return KS[n][capacity];
}
测试
var values = [3,4,5,8,10];
var weights = [2,3,4,5,9];
var capacity = 20;
var n = values.length;
console.log(kanpSack(capacity, weights, values, n)); //26
这个算法构造了一个二维表格KS，存储了递归过程的中的值，即用for循环代替了递归，表格右下角的最后一个格子就是问题的解。
网友评论