动态规划

思想

通过把问题分解成子问题，再根据子问题的解得出原问题的解。
例如：1+1+1 = 3，1+1+1+2 = 5。因为(1+1+1)+2 = 3 + 2 = 5。
这时我们可以把每次计算过的值给存起来，这样下次计算时就不用重新计算。

用最少的东西拿需求的重量

假设有个包，现在有1, 3, 3, 4四样东西，如何在规定的重量内拿到最少的物品。
假设需要拿6重量的东西，如果用贪心就会拿到[4, 1, 1]，但是显然我们需要的是[3, 3]，这时就需要使用到上面的思想。

• 如果拿1重量的东西，需要[1]
• 如果拿3重量的东西，需要[3]
• 如果拿4重量的东西，需要[4]
• 如果拿5重量的东西，需要[4, 1]
• 如果拿6重量的东西，有[3, 3]和[4, 1, 1]两种解法，这时就需判是否有更优解。

代码：

print = (key) => console.log(key)
class Package {
  constructor(things) {
    this.things = things // 存放物品的数组
    this.cache = {} // 用于缓存
  }

  pick(weight) {
    if (weight == 0) return []
    let minWeight = []

    // 查询缓存
    if (this.cache[weight]) return this.cache[weight]

    for (let i = 0, len = this.things.length; i < len; i++) {
      // 除去当前重量
      let leftWeight = weight - this.things[i],
        newMinWeight
      if (leftWeight >= 0) {
        // 用剩下的重量去查询
        newMinWeight = this.pick(leftWeight)

        // 如果查询到的比现在的数组长度更短，更换数组
        if (newMinWeight.length < minWeight.length || minWeight.length == 0)
          minWeight = [this.things[i]].concat(newMinWeight)
      }
    }

    // 存放至缓存中
    return (this.cache[weight] = minWeight)
  }
}

测试：

var package = new Package([1, 3, 3, 4])
print(package.pick(6)) // [3, 3]
print(package.pick(10)) // [4, 3, 3]