有 N 件物品和一个容量是 V 的背包。每件物品有且只有一件。
第 i 件物品的体积是 v ，价值是 w 。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
示例 1：
输入: N = 3, V = 4, v = [4,2,3], w = [4,2,3]
输出: 4
解释: 只选第一件物品，可使价值最大。
示例 2：
输入: N = 3, V = 5, v = [4,2,3], w = [4,2,3]
输出: 5
解释: 不选第一件物品，选择第二件和第三件物品，可使价值最大。
这是最为基础的背包问题，每种物品只有一件，可以选择取或者不取。
问题描述可以归结为：将N种物品有选择地放入容量为V的背包中，要求背包中的物品价值最大。
尝试提炼其子问题：将i种物品有选择地放入容量为V的背包中，要求背包中的物品价值最大。
那么由子问题转移到父问题的方程为：
f(i,V) = max{f(i-1,V), f(i-1,V-v[i]) + w[i]}
解释如下：“将前i件物品放入容量为V的背包中”这个子问题，若只考虑第i件物品的策略（放或者不放），那么就可以转化为一个只关系到前i-1件物品的问题。
- 如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”；
- 如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为V-v的背包中”，此时能获得的最大价值就是f(i-1, V-v)再加上通过放入第i件物品获得的价值w。
时间复杂度已经无法优化，我们可以尝试优化空间复杂度。
观察状态转移方程，发现当前状态i只和前一个状态有关i-1，那么我们可以用滚动数组，逆序遍历的方式进行空间优化。
function knapsack(weights, values, W){
var n = weights.length -1
var f = [[]]
for(var j = 0; j <= W; j++){
if(j < weights[0]){ //如果容量不能放下物品0的重量，那么价值为0
f[0][j] = 0
}else{ //否则等于物体0的价值
f[0][j] = values[0]
}
}
for(var j = 0; j <= W; j++){
for(var i = 1; i <= n; i++ ){
if(!f[i]){ //创建新一行
f[i] = []
}
if(j < weights[i]){ //等于之前的最优值
f[i][j] = f[i-1][j]
}else{
f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]] + values[i])
}
}
}
return f[n][W]
}
var a = knapsack([2,2,6,5,4],[6,3,5,4,6],10)
console.log(a)
合并循环
现在方法里面有两个大循环，它们可以合并成一个。
function knapsack(weights, values, W){
var n = weights.length;
var f = new Array(n)
for(var i = 0 ; i < n; i++){
f[i] = []
}
for(var i = 0; i < n; i++ ){
for(var j = 0; j <= W; j++){
if(i === 0){ //第一行
f[i][j] = j < weights[i] ? 0 : values[i]
}else{
if(j < weights[i]){ //等于之前的最优值
f[i][j] = f[i-1][j]
}else{
f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]] + values[i])
}
}
}
}
return f[n-1][W]
}
然后我们再认真地思考一下，为什么要孤零零地专门处理第一行呢？f[j] = j < weights ? 0 : values是不是能适用于下面这一行f[j] = Math.max(f[i-1][j], f[i-1][j-weights] + values) 。Math.max可以轻松转换为三元表达式，结构极其相似。而看一下i-1的边界问题，有的书与博客为了解决它，会添加第0行，全部都是0，然后i再往下挪。其实我们也可以添加一个${-1}$行。那么在我们的方程中就不用区分${i==0}$与${0>0}$的情况，方程与其他教科书的一模一样了！
function knapsack(weights, values, W){
var n = weights.length;
var f = new Array(n)
f[-1] = new Array(W+1).fill(0)
for(var i = 0 ; i < n ; i++){ //注意边界，没有等号
f[i] = new Array(W).fill(0)
for(var j=0; j<=W; j++){//注意边界，有等号
if( j < weights[i] ){ //注意边界， 没有等号
f[i][j] = f[i-1][j]
}else{
f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]]+values[i]);//case 3
}
}
}
return f[n-1][W]
}
选择物品
上面讲解了如何求得最大价值，现在我们看到底选择了哪些物品，这个在现实中更有意义。许多书与博客很少提到这一点，就算给出的代码也不对，估计是在设计状态矩阵就出错了。
仔细观察矩阵，从${f(n-1,W)}$逆着走向${f(0,0)}$，设i=n-1,j=W，如果${f(i,j)}$==${f(i-1,j-w_i)+v_i}$说明包里面有第i件物品，因此我们只要当前行不等于上一行的总价值，就能挑出第i件物品，然后j减去该物品的重量，一直找到j = 0就行了。
function knapsack(weights, values, W){
var n = weights.length;
var f = new Array(n)
f[-1] = new Array(W+1).fill(0)
var selected = [];
for(var i = 0 ; i < n ; i++){ //注意边界，没有等号
f[i] = [] //创建当前的二维数组
for(var j=0; j<=W; j++){ //注意边界，有等号
if( j < weights[i] ){ //注意边界， 没有等号
f[i][j] = f[i-1][j]//case 1
}else{
f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]]+values[i]);//case 2
}
}
}
var j = W, w = 0
for(var i=n-1; i>=0; i--){
if(f[i][j] > f[i-1][j]){
selected.push(i)
console.log("物品",i,"其重量为", weights[i],"其价格为", values[i])
j = j - weights[i];
w += weights[i]
}
}
console.log("背包最大承重为",W," 现在重量为", w, " 总价值为", f[n-1][W])
return [f[n-1][W], selected.reverse() ]
}
var a = knapsack([2,3,4,1],[2,5,3, 2],5)
console.log(a)
var b = knapsack([2,2,6,5,4],[6,3,5,4,6],10)
console.log(b)
使用滚动数组压缩空间
所谓滚动数组，目的在于优化空间，因为目前我们是使用一个${ij}$的二维数组来储存每一步的最优解。在求解的过程中，我们可以发现，当前状态只与前一行的状态有关，那么更之前存储的状态信息已经无用了，可以舍弃的，我们只需要存储当前状态和前一行状态，所以只需使用${2j}$的空间，循环滚动使用，就可以达到跟${i*j}$一样的效果。这是一个非常大的空间优化。
function knapsack(weights, values, W){
var n = weights.length
var lineA = new Array(W+1).fill(0)
var lineB = [], lastLine = 0, currLine
var f = [lineA, lineB]; //case1 在这里使用es6语法预填第一行
for(var i = 0; i < n; i++){
currLine = lastLine === 0 ? 1 : 0 //决定当前要覆写滚动数组的哪一行
for(var j=0; j<=W; j++){
f[currLine][j] = f[lastLine][j] //case2 等于另一行的同一列的值
if( j>= weights[i] ){
var a = f[lastLine][j]
var b = f[lastLine][j-weights[i]] + values[i]
f[currLine][j] = Math.max(a, b);//case3
}
}
lastLine = currLine//交换行
}
return f[currLine][W];
}
var a = knapsack([2,3,4,1],[2,5,3, 2],5)
console.log(a)
var b = knapsack([2,2,6,5,4],[6,3,5,4,6],10)
console.log(b)
注意，这种解法由于丢弃了之前N行的数据，因此很难解出挑选的物品，只能求最大价值。
递归法解01背包
function knapsack(n, W, weights, values, selected) {
if (n == 0 || W == 0) {
//当物品数量为0，或者背包容量为0时，最优解为0
return 0;
} else {
//从当前所剩物品的最后一个物品开始向前，逐个判断是否要添加到背包中
for (var i = n - 1; i >= 0; i--) {
//如果当前要判断的物品重量大于背包当前所剩的容量，那么就不选择这个物品
//在这种情况的最优解为f(n-1,C)
if (weights[i] > W) {
return knapsack(n - 1, W, weights, values, selected);
} else {
var a = knapsack(n - 1, W, weights, values, selected); //不选择物品i的情况下的最优解
var b = values[i] + knapsack(n - 1, W - weights[i], weights, values, selected); //选择物品i的情况下的最优解
//返回选择物品i和不选择物品i中最优解大的一个
if (a > b) {
selected[i] = 0; //这种情况下表示物品i未被选取
return a;
} else {
selected[i] = 1; //物品i被选取
return b;
}
}
}
}
}
var selected = [], ws = [2,2,6,5,4], vs = [6,3,5,4,6]
var b = knapsack( 5, 10, ws, vs, selected)
console.log(b) //15
selected.forEach(function(el,i){
if(el){
console.log("选择了物品"+i+ " 其重量为"+ ws[i]+" 其价值为"+vs[i])
}
})
