essay | tech | year-summary | about

返回上级菜单

dp (dynamic programming)

日期：2020-10-29T00:00:00Z

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

出自「蟻本」

例子：

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

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

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

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