ps:之前的code写错了,我忏悔。


一直是我短板的dp问题,看起来一直把它放着也不是什么好事。
这篇文章会持续连载,连载典型的dp问题。
代码会在这里连载:https://github.com/candywater/ProCon/tree/master/originals/

Knapsack 问题

经典中的经典,大学课堂应该都教过的。
由于问题比较简单,不过过多说明,只当是给初学者学习的例子。

问题1

有N个物品,分别重W_i斤和价值v_i元。求这些物品在不超过数值A范围时的最大价格。
限制:1 <= N <= 100, 1 <= A <= 10000, 1 <= w_i, v_i <= 100

出自「蟻本」

例子:

1
2
3
4
INPUT:
n = 4
(w, v) = {(2, 3), (1, 2), (3, 4), (2, 2)}
A = 5

先来完全的遍历法

https://github.com/candywater/ProCon/blob/master/originals/knapsack01/00.js

1
2
3
4
5
6
7
8
9
10
11
function rec(boollist, i){
  if(i >= boollist.length){
    // 略
    return 
  }

  boollist[i] = false;
  rec(boollist, i+1)
  boollist[i] = true;
  rec(boollist, i+1)
}

解答思路

以重量为基准,解决在重量x下的最优解,以此来求最大解。 (bottom - up解法)

https://github.com/candywater/ProCon/blob/master/originals/knapsack01/01.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function knapsack_multi(){
  // 略
  // dp 
  // bottom - up
  for (var i = w.length-1; i >= 0; i--) {
    for (var j = maxWeight-1; j >= 0; j--) {
      if (j + w[i - 1] > maxWeight)
        dp[i][j] = dp[i - 1][j];
      else
        dp[i][j] = max(dp[i - 1][j], dp[i-1][j + w[i - 1]] + v[i - 1]);
    }
  }
  console.log(dp[0][targetW])
}

同样,这题的top - down解法是这样的

https://github.com/candywater/ProCon/blob/master/originals/knapsack01/02.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function knapsack_multi(){
  // 略
  // dp 
  // top - down
  for (var i = w.length-1; i >= 0; i--) {
    for (var j = maxWeight-1; j >= 0; j--) {
      if (j - w[i] < 0)
        dp[i][j] = dp[i + 1][j];
      else
        dp[i][j] = max(dp[i + 1][j], dp[i+1][j - w[i]] + v[i]);
    }
  }
  console.log(dp[0][targetW])
}

Ref


creativ common license