java中揹包的貪婪算法

Question

我想爲揹包問題編寫一個非常簡單的貪婪算法。我的輸入是兩個平行的數組。一個數組包含項目的值，另一個數組包含權重。

我試圖寫的貪婪算法如下：檢查哪個項目具有最高值並將其放入揹包中。然後將此項目的值設置爲零。如果揹包仍然可以拿着它，再次檢查哪個物品具有最高價值並將其放入揹包中。如果它可以保持它，請將該值再次設置爲零（放入後），然後再次開始查找最高值。如果那個揹包不能拿住它，那麼就結束這個程序。

我知道有很多更好的貪婪算法，但在我看來這是一個非常簡單的算法，我想我可以管理它。我的問題是，我必須通過整個值數組來找到最大值。然後，當我找到它時，我把它放在揹包裏，並將其值設爲零。但問題是我必須回到for循環才能找到新的最高價值物品並將其放入揹包中。但我不知道如何去做這件事。

我正在用Java寫這篇文章。

Answer 1

首先，你通常用貪婪的方式解決揹包問題，即通過使用最高的比率值/重量而不是價值。

其次，如果您對項目列表進行一次排序並逐步瀏覽，則無需在每個步驟中搜索最大值。