跳轉至
紙質書（簡體中文版）已發行，詳情請見這裡

# 15.6 練習

## 15.6.1 知識鞏固

### 1. 每次選最大硬幣一定最好嗎

硬幣面值為 `[1, 7, 10]`，目標金額為 14。

1. 按“每次取不超過剩餘金額的最大面值”執行，寫出所取硬幣；
2. 是否存在使用更少硬幣的方案？如果存在，請寫出一種；如果不存在，請說明理由；
3. 這能否說明該貪婪策略對任意硬幣面值都正確？

參考答案

1. 貪婪依次選擇 `10 + 1 + 1 + 1 + 1`，共 5 枚硬幣。

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

3. 不能。這個反例說明，對任意硬幣面值，每次選擇當前能取的最大面值並不一定得到最少硬幣數； 眼前最大的選擇可能破壞後續更好的組合。

### 2. 背包應該先裝哪件物品

一個容量為 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。

### 3. 兩個指標下一步怎樣移動

隔板高度為 `[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. 移動較短隔板對應的指標，才仍有可能得到更大的容量。移動較長隔板後，兩塊隔板的距離一定縮短，而容器高度仍受未移動的短板限制， 只可能不變或變小。因此容量不可能超過移動前；只有移動短板，才有機會遇到更高的隔板。

## 15.6.2 程式設計練習

### 1. 分數背包

給定等長陣列 `wgt` 和 `val`，其中 `wgt[i] > 0`、`val[i] >= 0`，背包容量 `cap >= 0`。 每種物品只有一件，但允許只裝入其中一部分， 獲得的價值按所裝重量佔該物品總重量的比例計算。請使用貪婪演算法， 並以實數返回背包能夠獲得的最大總價值。

解題提示

1. 先計算每件物品的單位重量價值 val[i] / wgt[i]，除法結果要保留小數
2. 單位價值越高的物品越先裝入背包
3. 若剩餘容量小於當前物品重量，就裝入恰好填滿背包的部分並結束

##### 歡迎在評論區留下你的見解、問題或建議