DP-01背包

问题分析：

使用一个数组，将计算过的值存起来。如果之后再次访问，直接返回计算后的值。

代码实现：

/**
 * * @param {number[][]} arr - (weight, value)[]
 * @param {number} maxHeavy - The max weight can be picked.
 */ function resolve(arr, maxHeavy) {
  const len = arr.length
  const dp = new Array(10000).fill(null).map(() => new Array(10000).fill(-1))

  /**
   * @param {number} index - Current index
   * @param {number} current - The last heavy.
   */ function traverse(index, current) {
    if (dp[index][current] >= 0) return dp[index][current]

    let res
    if (index === len) {
      res = 0
    } else if (current < arr[index][0]) {
      res = traverse(index + 1, current)
    } else {
      res = Math.max(
        traverse(index + 1, current),
        traverse(index + 1, current - arr[index][0]) + arr[index][1]
      )
    }

    return (dp[index][current] = res)
  }

  return traverse(0, maxHeavy)
}

console.log(
  resolve(
    [
      [2, 3],
      [1, 2],
      [3, 4],
      [2, 2],
    ],
    5
  )
)

目录