有什麼想法來優化貪婪算法嗎？

我最近編寫了一個程序來解決使用Python的揹包問題。它的偉大工程，一般遵循貪心算法（即找出每一步的最佳解決方案，直到它結束）有什麼想法來優化貪婪算法嗎？

但我需要優化它基於貪心算法（這是我的功課的一部分）上

那麼你能否給我提供一些基本的想法來改進它？

Item Name    Weight   Profit 
    Ammunition    3.00   95.00 
    Bread     3.60   90.00 
    Firewood    2.50   56.00 
    Olive Oil    2.40   45.00 
    Water     3.70   67.00 
    Weapon     4.80   79.73

這是我目前項目的輸出。袋子容量限制爲20kg，數據無法更改，但我需要一個更好的主意來改進它。謝謝！

我不知道有關的代碼或解決方案，但我認爲這完全是與「效率」

來源

2012-03-14 XIA Yang

與所有家庭作業一樣，您可以隨時查看http://en.wikipedia.org/wiki/Knapsack_problem - 查看動態編程部分的靈感 – 2012-03-14 23:19:55

優化代碼或解決方案？ – 2012-03-14 23:21:35

在這裏，我將使用術語「空間」和「重量」的同義詞。

您可以做的一件事是計算每個項目的比率profit/weight。比例差異在一定空間內是該空間的最佳可能改進。例如，如果您有空的空間，並且如果您重新排列，則可能能夠擠入其他某個項目Z，那麼您可以從該空間獲得的最大利潤爲（Zratio-0比率）*權重。因此，您可以基於貪婪算法生成候選解決方案，然後使用它來限制可能的改進。一般來說，你會想從動態編程的角度來看待這個問題。

來源

2012-03-14 23:24:39 ninjagecko

你幫了我很多，我會進一步研究動態編程，感謝U – 2012-03-14 23:32:49

@XIAYang：我提到的是限制你的搜索的方法之一，它與DP是分開的，你確實需要先理解。沒問題。 – ninjagecko 2012-03-14 23:52:57

有什麼想法來優化貪婪算法嗎？

回答

相關問題