练习

知识巩固

每次选最大硬币一定最好吗

硬币面值为 [1, 7, 10]，目标金额为 14。

1. 按“每次取不超过剩余金额的最大面值”执行，写出所取硬币；
2. 是否存在使用更少硬币的方案？如果存在，请写出一种；如果不存在，请说明理由；
3. 这能否说明该贪心策略对任意硬币面值都正确？

参考答案

1. 贪心依次选择 10 + 1 + 1 + 1 + 1，共 5 枚硬币。

2. 存在使用更少硬币的方案：7 + 7，只需 2 枚硬币。

3. 不能。这个反例说明，对任意硬币面值，每次选择当前能取的最大面值并不一定得到最少硬币数； 眼前最大的选择可能破坏后续更好的组合。

背包应该先装哪件物品

一个容量为 4 千克的背包中可以装入以下物品，物品允许只取一部分， 所取价值与重量成正比：

• 物品 A：重量 4 千克，价值 20；
• 物品 B：重量 3 千克，价值 18。

1. 两件物品每千克的价值分别是多少？应先装哪一件？
2. 按分数背包的贪心策略装满背包，最终价值是多少？
3. 在物品可以切分、背包限制总重量的情况下，选择物品时应该比较总价值还是每千克价值？为什么？

参考答案

1. A 每千克价值为 20 ÷ 4 = 5，B 每千克价值为 18 ÷ 3 = 6， 因此应先装单位价值更高的 B。

2. 先装入全部 B，占用 3 千克、获得价值 18；剩余 1 千克容量， 再装入 1 千克 A，获得价值 5。最终价值为 18 + 5 = 23。

3. 背包限制的是总重量，而且物品可以切分，所以应比较单位重量的价值。 A 的总价值虽然更高，但每千克价值低于 B；若先装满 A，只能得到价值 20。

两个指针下一步怎样移动

隔板高度为 [1, 8, 6, 2, 5]，用首尾双指针寻找最大容量。 容量等于“两块隔板中较短者的高度 × 两块隔板的下标距离”。

1. 初始时左指针在下标 0、右指针在下标 4，当前容量是多少？下一步应移动哪个指针？
2. 按照第 1 问的选择移动一次后，两个指针分别位于哪个下标？此时容量是多少？下一步又应移动哪个指针？
3. 在当前一对隔板中，可以移动较短隔板对应的指针，也可以移动较长隔板对应的指针。哪一种移动仍有可能得到更大的容量？为什么？

参考答案

1. 当前容量为 min(1, 5) × (4 - 0) = 4。左侧隔板较短，因此移动左指针。

2. 移动左指针后，两个指针分别位于下标 1 和 4。当前容量为 min(8, 5) × (4 - 1) = 15。右侧隔板较短，因此下一步移动右指针。

3. 移动较短隔板对应的指针，才仍有可能得到更大的容量。移动较长隔板后，两块隔板的距离一定缩短，而容器高度仍受未移动的短板限制， 只可能不变或变小。因此容量不可能超过移动前；只有移动短板，才有机会遇到更高的隔板。

编程练习

分数背包

给定等长数组 wgt 和 val，其中 wgt[i] > 0、val[i] >= 0，背包容量 cap >= 0。 每种物品只有一件，但允许只装入其中一部分， 获得的价值按所装重量占该物品总重量的比例计算。请使用贪心算法， 并以实数返回背包能够获得的最大总价值。

解题提示

1. 先计算每件物品的单位重量价值 val[i] / wgt[i]，除法结果要保留小数
2. 单位价值越高的物品越先装入背包
3. 若剩余容量小于当前物品重量，就装入恰好填满背包的部分并结束