15.6   練習¶

15.6.1   知識鞏固¶

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

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

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

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

一個容量為 4 千克的背包中可以裝入以下物品，物品允許只取一部分， 所取價值與重量成正比：

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

1. 兩件物品每千克的價值分別是多少？應先裝哪一件？
2. 按分數背包的貪婪策略裝滿背包，最終價值是多少？
3. 在物品可以切分、背包限制總重量的情況下，選擇物品時應該比較總價值還是每千克價值？為什麼？

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

隔板高度為 [1, 8, 6, 2, 5]，用首尾雙指標尋找最大容量。 容量等於“兩塊隔板中較短者的高度 × 兩塊隔板的下標距離”。

1. 初始時左指標在下標 0、右指標在下標 4，當前容量是多少？下一步應移動哪個指標？
2. 按照第 1 問的選擇移動一次後，兩個指標分別位於哪個下標？此時容量是多少？下一步又應移動哪個指標？
3. 在當前一對隔板中，可以移動較短隔板對應的指標，也可以移動較長隔板對應的指標。哪一種移動仍有可能得到更大的容量？為什麼？

15.6.2   程式設計練習¶

1.   分數背包¶

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

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