动态规划一般是处理在限制条件下（背包总重量）能够最多能够拿多少东西的问题。在这个基础上，又可以扩展成最大价值是多少，最大价值具体为哪些物品，物品附带子物品的情况。

基础版

先说最简单的背包问题。假如有一个能够背20公斤的背包，现在有4个物品，分别为2， 5， 10， 11公斤，最多能够背多少公斤？

可以暴力穷举，当然效率会低很多。换用动态规则，根据状态转移表，新单元格的重量为上一个单元格的值和当前商品的值+剩余背包的值。下面就是代码来解释。

units = [5, 10, 2, 11]
total = 20

# 状态转移表记录价值和物品
# 每一行代表一个物品
# 每一列表示背包重量，一共21列
dp = (0..(units.size)).map { [0] * (total + 1) }

(1..units.size).each do |i|
  (1..total).each do |j|
    # 遍历每个单元格
    # 如果当前背包重量大于当前物品重量，则应用转移公式
    # 否则就直接直接用上一单元格的值
    unit_w = units[i-1]
    if j >= unit_w
      # 如果背包重量大于当前物品重量，则取要和不要两种情况的最大值
      t = dp[i-1][j-unit_w] + unit_w #要的情况
      dp[i][j] = [t, dp[i-1][j]].max
    else
      dp[i][j] = dp[i-1][j]
    end
  end
end

p dp[-1][-1]

升级版

如果每个物品都有不同的价值，要求价值最大化呢？只需要在状态转移表里面记录价值就行了。注意下面的dp[i][j] = [dp[i-1][j], dp[i-1][j - items[i-1][0]] + items[i-1][1]].max，依旧是当前商品的值+剩余背包的值。

items = [[8, 16], [4, 12], [5, 10]]
total_amt = 10

dp = (0..items.size).map { [0] * (total_amt + 1) }

(1..items.size).each do |i|
  (1..total_amt).each do |j|
    # 如果当前金额不足购买当前item
    if j < items[i-1][0]
        dp[i][j] = dp[i-1][j]
    else
        dp[i][j] = [dp[i-1][j], dp[i-1][j - items[i-1][0]] + items[i-1][1]].max
    end
  end
end

p dp

我无视价值，只需要数量最多

状态转移表内记录数量就行了。

units = [5, 10, 2, 11]
total = 20

dp = (0..(units.size)).map { [0] * (total + 1) }

(1..units.size).each do |i|
  (1..total).each do |j|
    unit_w = units[i-1]
    if j >= unit_w
      t = dp[i-1][j-unit_w] + 1
      dp[i][j] = [t, dp[i-1][j]].max
    else
      dp[i][j] = dp[i-1][j]
    end
  end
end

p dp[-1]

我想知道我到底买了哪些商品

只需要在状态表中记录转移的过程。

units = [5, 10, 2, 11]
total = 20

# 单元格第一个元素是重量，第二个是对应的物品
dp = (0..(units.size)).map { (0..total).map { [0, []] } }

(1..units.size).each do |i|
  (1..total).each do |j|
    unit_w = units[i-1]
    if j >= unit_w
      t = dp[i-1][j-unit_w][0] + unit_w
      if t > dp[i-1][j][0]
        dp[i][j] = [t, dp[i-1][j-unit_w][1] + [unit_w]]
      else
        dp[i][j] = dp[i-1][j]
      end
    else
      dp[i][j] = dp[i-1][j]
    end
  end
end

p dp[-1]