# JavaScript 背包问题详解

#### 引子

##### 1.2 问题分析：

w

v

i

0

1

2

3

4

5

6

7

8

9

10

2

6

0

2

3

1

6

5

2

5

4

3

4

6

4

w

v

i

0

1

2

3

4

5

6

7

8

9

10

2

6

0

0

0

6

6

6

6

6

6

6

6

6

2

3

1

6

5

2

5

4

3

4

6

4

w

v

i

0

1

2

3

4

5

6

7

8

9

10

2

6

0

0

0

6

6

6

6

6

6

6

6

6

2

3

1

0

0

6

6

9

9

9

9

9

9

9

6

5

2

5

4

3

4

6

4

w

v

i

0

1

2

3

4

5

6

7

8

9

10

2

6

0

0

0

6

6

6

6

6

6

6

6

6

2

3

1

0

0

6

6

9

9

9

9

9

9

9

6

5

2

0

0

6

6

9

9

9

9

11

11

14

5

4

3

4

6

4

w

v

i

0

1

2

3

4

5

6

7

8

9

10

2

6

0

0

0

6

6

6

6

6

6

6

6

6

2

3

1

0

0

6

6

9

9

9

9

9

9

9

6

5

2

0

0

6

6

9

9

9

9

11

11

14

5

4

3

0

0

6

6

9

9

9

10

11

13

14

4

6

4

0

0

6

6

9

9

12

12

15

15

15

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)
##### 1.3 各种优化：

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]
}

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]
}

w

v

i

0

1

2

3

4

5

6

7

8

9

10

X

X

-1

0

0

0

0

0

0

0

0

0

0

0

2

6

0

0

0

6

6

6

6

6

6

6

6

6

2

3

1

0

0

6

6

9

9

9

9

9

9

9

6

5

2

0

0

6

6

9

9

9

9

11

11

14

5

4

3

0

0

6

6

9

9

9

10

11

13

14

4

6

4

0

0

6

6

9

9

12

12

15

15

15

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)

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)

weights为每个物品的重量，values为每个物品的价值，W是背包的容量，i表示要放进第几个物品，j是背包现时的容量（假设我们的背包是魔术般的可放大，从0变到W）。

f中的-1就变成没有意义，因为没有第-1行，而weights[0], values[0]继续有效，${f(0,j)}$也有意义，因为我们全部放到一个一维数组中。于是:

javascript实现：

function knapsack(weights, values, W){
var n = weights.length;
var f = new Array(W+1).fill(0)
for(var i = 0; i < n; i++) {
for(var j = W; j >= weights[i]; j--){
f[j] = Math.max(f[j], f[j-weights[i]] +values[i]);
}
console.log(f.concat()) //调试
}
return f[W];
}
var b = knapsack([2,2,6,5,4],[6,3,5,4,6],10)
console.log(b)
##### 1.4 递归法解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])
}
})

#### 完全背包问题

##### 2.2 问题分析：

for(var i = 0 ; i < n ; i++){
for(var j=0; j<=W; j++){
f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]]+values[i]))
}
}
}

for(var i = 0 ; i < n ; i++){
for(var j=0; j<=W; j++){
for(var k = 0; k < j / weights[i]; k++){
f[i][j] = Math.max(f[i-1][j], f[i-1][j-k*weights[i]]+k*values[i]))
}
}
}
}

javascript的完整实现：

function completeKnapsack(weights, values, W){
var f = [], n = weights.length;
f[-1] = [] //初始化边界
for(var i = 0; i <= W; i++){
f[-1][i] = 0
}
for (var i = 0;i < n;i++){
f[i] = new Array(W+1)
for (var j = 0;j <= W;j++) {
f[i][j] = 0;
var bound = j / weights[i];
for (var k = 0;k <= bound;k++) {
f[i][j] = Math.max(f[i][j], f[i - 1][j - k * weights[i]] + k * values[i]);
}
}
}
return f[n-1][W];
}
//物品个数n = 3，背包容量为W = 5，则背包可以装下的最大价值为40.
var a = completeKnapsack([3,2,2],[5,10,20], 5)
console.log(a) //40
##### 2.3 O(nW)优化

javascript的完整实现：

function unboundedKnapsack(weights, values, W) {
var f = [],
n = weights.length;
f[-1] = []; //初始化边界
for (let i = 0; i <= W; i++) {
f[-1][i] = 0;
}
for (let i = 0; i < n; i++) {
f[i] = [];
for (let 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][j - weights[i]] + values[i]);
}
}
console.log(f[i].concat());//调试
}
return f[n - 1][W];
}

var a = unboundedKnapsack([3, 2, 2], [5, 10, 20], 5); //输出40
console.log(a);
var b = unboundedKnapsack([2, 3, 4, 7], [1, 3, 5, 9], 10); //输出12
console.log(b);

function unboundedKnapsack(weights, values, W) {
var n = weights.length,
f = new Array(W + 1).fill(0);
for(var i=0; i< n; ++i){
for(j = weights[i]; j <= W; ++j) {
var tmp = f[j-weights[i]]+values[i];
f[j] = (f[j] > tmp) ? f[j] : tmp;
}
}
console.log(f)//调试
return f[W];
}
var a = unboundedKnapsack([3, 2, 2], [5, 10, 20], 5); //输出40
console.log(a);
var b = unboundedKnapsack([2, 3, 4, 7], [1, 3, 5, 9], 10); //输出12
console.log(b);

#### 多重背包问题

##### 3.2 问题分析：

function knapsack(weights, values, numbers,  W){
var n = weights.length;
var f= new Array(W+1).fill(0)
for(var i = 0; i < n; i++) {
for(var k=0; k<numbers[i]; k++)//其实就是把这类物品展开，调用numbers[i]次01背包代码
for(var j=W; j>=weights[i]; j--)//正常的01背包代码
f[j]=Math.max(f[j],f[j-weights[i]]+values[i]);
}
return f[W];
}
var b = knapsack([2,3,1 ],[2,3,4],[1,4,1],6)
console.log(b)
##### 3.3 使用二进制优化

定理：一个正整数n可以被分解成1,2,4,…,2^(k-1),n-2^k+1（k是满足n-2^k+1>0的最大整数）的形式，且1～n之内的所有整数均可以唯一表示成1,2,4,…,2^(k-1),n-2^k+1中某几个数的和的形式。

（1） 数列1,2,4,…,2^(k-1),n-2^k+1中所有元素的和为n，所以若干元素的和的范围为：[1, n]；

（2）如果正整数t<= 2^k – 1,则t一定能用1,2,4,…,2^(k-1)中某几个数的和表示，这个很容易证明：我们把t的二进制表示写出来，很明显，t可以表示成n=a0*2^0+a1*2^1+…+ak*2^（k-1），其中ak=0或者1，表示t的第ak位二进制数为0或者1.

（3）如果t>=2^k,设s=n-2^k+1，则t-s<=2^k-1，因而t-s可以表示成1,2,4,…,2^(k-1)中某几个数的和的形式，进而t可以表示成1,2,4,…,2^(k-1)，s中某几个数的和（加数中一定含有s）的形式。

（证毕！）
function mKnapsack(weights, values, numbers, W) {
var kind = 0; //新的物品种类
var ws = []; //新的物品重量
var vs = []; //新的物品价值
var n = weights.length;
/**
* 二进制分解
* 100=1+2+4+8+16+32+37，观察可以得出100以内任何一个数都可以由以上7个数选择组合得到，
* 所以对物品数目就不是从0都100遍历，而是0，1，2，4，8，16，32，37遍历，时间大大优化。
*/
for (let i = 0; i < n; i++) {
var w = weights[i];
var v = values[i];
var num = numbers[i];
for (let j = 1; ; j *= 2) {
if (num >= j) {
ws[kind] = j * w;
vs[kind] = j * v;
num -= j;
kind++;
} else {
ws[kind] = num * w;
vs[kind] = num * v;
kind++;
break;
}
}
}
//01背包解法
var f = new Array(W + 1).fill(0);
for (let i = 0; i < kind; i++) {
for (let j = W; j >= ws[i]; j--) {
f[j] = Math.max(f[j], f[j - ws[i]] + vs[i]);
}
}
return f[W];
}

var b = mKnapsack([2,3,1 ],[2,3,4],[1,4,1],6)
console.log(b) //9

#### 参考链接

• http://www.ahathinking.com/archives/95.html
• http://www.hawstein.com/posts/f-knapsack.html
• http://blog.csdn.net/shuilan0066/article/details/7767082
• http://blog.csdn.net/siyu1993/article/details/52858940
• http://blog.csdn.net/Dr_Unknown/article/details/51275471
• https://www.cnblogs.com/shimu/p/5667215.html
• http://www.saikr.com/t/2147
• https://www.cnblogs.com/tgycoder/p/5329424.html
• http://blog.csdn.net/chuck001002004/article/details/50340819
• https://www.cnblogs.com/favourmeng/archive/2012/09/07/2675580.html

241 篇文章49 人订阅

0 条评论

## 相关文章

### 每周学点大数据 | No.3算法设计与分析理论

No.3期 算法设计与分析理论 在计算机科学中，研究算法的设计和评价算法“好坏”的分支，称为算法设计与分析理论。它研究如何去设计解决问题的算法，同时给出一个对...

30210

7691

### 01背包和完全背包，一维dp存储区别

对01背包问题，n个物品背包容量为v，第i个物品的价值为v[i],重量w[i]

1221

3179

3937

2535

1266

983

5922

2958