15.6 练习¶
15.6.1 知识巩固¶
1. 每次选最大硬币一定最好吗¶
硬币面值为 [1, 7, 10]，目标金额为 14。
- 按“每次取不超过剩余金额的最大面值”执行，写出所取硬币；
- 是否存在使用更少硬币的方案？如果存在，请写出一种；如果不存在，请说明理由；
- 这能否说明该贪心策略对任意硬币面值都正确？
参考答案
-
贪心依次选择
10 + 1 + 1 + 1 + 1，共 5 枚硬币。 -
存在使用更少硬币的方案：
7 + 7，只需 2 枚硬币。 -
不能。这个反例说明，对任意硬币面值，每次选择当前能取的最大面值并不一定得到最少硬币数； 眼前最大的选择可能破坏后续更好的组合。
2. 背包应该先装哪件物品¶
一个容量为 4 千克的背包中可以装入以下物品，物品允许只取一部分， 所取价值与重量成正比：
- 物品 A：重量 4 千克，价值 20；
- 物品 B：重量 3 千克，价值 18。
- 两件物品每千克的价值分别是多少？应先装哪一件？
- 按分数背包的贪心策略装满背包，最终价值是多少？
- 在物品可以切分、背包限制总重量的情况下，选择物品时应该比较总价值还是每千克价值？为什么？
参考答案
-
A 每千克价值为
20 ÷ 4 = 5，B 每千克价值为18 ÷ 3 = 6， 因此应先装单位价值更高的 B。 -
先装入全部 B，占用 3 千克、获得价值 18；剩余 1 千克容量， 再装入 1 千克 A，获得价值 5。最终价值为
18 + 5 = 23。 -
背包限制的是总重量，而且物品可以切分，所以应比较单位重量的价值。 A 的总价值虽然更高，但每千克价值低于 B；若先装满 A，只能得到价值 20。
3. 两个指针下一步怎样移动¶
隔板高度为 [1, 8, 6, 2, 5]，用首尾双指针寻找最大容量。
容量等于“两块隔板中较短者的高度 × 两块隔板的下标距离”。
- 初始时左指针在下标 0、右指针在下标 4，当前容量是多少？下一步应移动哪个指针？
- 按照第 1 问的选择移动一次后，两个指针分别位于哪个下标？此时容量是多少？下一步又应移动哪个指针？
- 在当前一对隔板中，可以移动较短隔板对应的指针，也可以移动较长隔板对应的指针。哪一种移动仍有可能得到更大的容量？为什么？
参考答案
-
当前容量为
min(1, 5) × (4 - 0) = 4。左侧隔板较短，因此移动左指针。 -
移动左指针后，两个指针分别位于下标 1 和 4。当前容量为
min(8, 5) × (4 - 1) = 15。右侧隔板较短，因此下一步移动右指针。 -
移动较短隔板对应的指针，才仍有可能得到更大的容量。移动较长隔板后，两块隔板的距离一定缩短，而容器高度仍受未移动的短板限制， 只可能不变或变小。因此容量不可能超过移动前；只有移动短板，才有机会遇到更高的隔板。
15.6.2 编程练习¶
1. 分数背包¶
给定等长数组 wgt 和 val，其中 wgt[i] > 0、val[i] >= 0，背包容量 cap >= 0。
每种物品只有一件，但允许只装入其中一部分，
获得的价值按所装重量占该物品总重量的比例计算。请使用贪心算法，
并以实数返回背包能够获得的最大总价值。
解题提示
- 先计算每件物品的单位重量价值 val[i] / wgt[i]，除法结果要保留小数
- 单位价值越高的物品越先装入背包
- 若剩余容量小于当前物品重量，就装入恰好填满背包的部分并结束