题目:
设物品有4个,即n=4. 背包能容纳的总重量为5,即W=5. 每个物品的重量分别为w=(2,3,3,3). 每个物品分别的价值为b=(3,4,5,6)，给出动态规划求解过程。
答:
- 思路:
- 物品不能被拆分, 每个物品要没放要么不放. 如果用穷举法有2^n种情况, 耗时较久, 题目也要求用动态规划来求解.
- 考虑最优子结构. 给每个物品编号, 从1到n. 设B(n, W)为n个物品的最大价值.
- 推导公式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)
-
自底向上, 计算过程:
image.png
- 结果: 选择第一个和最后一个物品, 最大价值为9.
网友评论