Python使用貪婪法及其改進演算法求解0-1背包問題

• 2019 年 11 月 22 日
• 筆記

貪婪法基本思想：

首先按物品單位價值（物品價值/物品重量或體積）降序排序，然後逐個嘗試是否能放進背包而不超過背包容量，直到遇到無法放入背包的物品就結束。

改進思路：

遇到放不進背包的物品就跳過去，看看排在後面的單位價值小的物品還有沒有能放進背包的。

參考程式碼：

運行結果：