动态规划-0、1背包问题

题目:

设物品有4个,即n=4. 背包能容纳的总重量为5,即W=5. 每个物品的重量分别为w=(2,3,3,3). 每个物品分别的价值为b=(3,4,5,6)，给出动态规划求解过程。

答:

• 思路:
  1. 物品不能被拆分, 每个物品要没放要么不放. 如果用穷举法有2^n种情况, 耗时较久, 题目也要求用动态规划来求解.
  2. 考虑最优子结构. 给每个物品编号, 从1到n. 设B(n, W)为n个物品的最大价值.
  3. 推导公式B(n, W).
     • a:如果第n个物品超过了袋子的重量w(即w(n) > W), 那么B(n, w) = B(n-1, w). 否则:
     • b:选择放第n个物品, B(n, W) = B(n-1, W-w(n))
     • c:选择不放第n个物品, B(n, W) = B(n-1, W)
     • 从b和c里面选择最大价值那个. 即 B(n, W) = max{B(n-1, W-w(n)), B(n-1, W)} (w(n) <= W)

  4. 自底向上, 计算过程:

     
     image.png
  5. 结果: 选择第一个和最后一个物品, 最大价值为9.