knapsack

做完爬楼梯问题后，我们继续挑战01背包问题，直接上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const cap = 100;
const count = 10;
const weights = [0, 20, 5, 30, 6,  15, 13, 10, 27, 17, 13];
const values =  [0, 20, 7, 25, 15, 30, 1,  7,  50, 40, 10];

let maps = [[0,0], [0,0]];

const getKnapsackValue = (cap, count, weights, values) => {
  for(let i = 1; i <= count; i++){
    for (let j = 1; j <= cap; j++) {
      maps[i] = maps[i] || [0];
      if(j < weights[i]){
        maps[i][j] = maps[i-1][j] || 0;
      }else{
        maps[i][j] = Math.max( maps[i-1][j] || 0, ( maps[i-1][j-weights[i]] || 0 )  + values[i]);
      }
    }
  }
}

getKnapsackValue(cap, count, weights, values)

console.log(maps[10][100])

代码能得出正确的答案，状态转移公式就不上了，网上全是。一些小心得：

1
2
1. weights values 和index遍历0位先填充0，方便遍历
2. maps[i][j]初始化用了一点不优雅的技巧。

这是最原始的版本，背包九讲里可知，O(n^2)时间复杂度是不能优化了，空间可以被优化，上面是O(n^2)