※ 引述《wsx02 ()》之銘言：
: 有7個物品要放入背包，但背包只能裝到重量15，物品只能選擇裝或不裝
: 要怎麼選才能讓這些物品的價值最大?
: 物品 A B C D E F G
: 價值 8 6 15 4 2 5 9
: 重量 2 3 5 4 4 2 6
: 答案是可以裝到價值總和34的物品
: 請問有人知道要怎麼選會比較快嗎?
: (這問題本來是演算法0/1 Knapsack的問題，只是要畫7*15的表格解會很花時間..)
: 謝謝
這是一個演算法的問題 應該沒有絕對哪種選法一次保證選到最好
是我我會這樣設計我的演算法
(1)定義CP值=價值/重量
(2)CP值高的先選
(3)最後做微調把重量15用完
物品 A B C D E F G
價值 8 6 15 4 2 5 9
重量 2 3 5 4 4 2 6
CP值 4 2 3 1 .52.51.5
選的順序A C F B G D E
重量2 5 2 3 6 4 4
ACF重量9(價值28) 加B重量12(價值34) 加G重量15(價值37)
所以照我的演算法選出來ACFG 總重量15 總價值37
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.252.193.225