algorithm - 貪欲なアルゴリズムを使用してナップザックの問題を追跡する方法は?

Question

問題は、次の情報を使用して貪欲なアルゴリズムでナップザックの問題を追跡する方法です。

P=[10,7,12,13,6,20]
W=[3,2,4,3,13,8]
M=15
n=6

誰かがこれを理解するのを手伝ってくれたり、正しい方向に向けてくれたりしてくれたら幸いです。

Answer 1

それが「フラクショナル ナップザック」 (つまり、アイテムの一部を取ることができる) であれば、簡単です。

アイテムは (価格、重量のペアとして) [(10, 3), (7, 2), (12, 4), (13, 3), (6, 13), (20, 8)] です。

直感的に、軽量で価格が高い商品を最初に購入する必要があります。それでは、価格と重量の比率でアイテムを並べ替えてみましょう。

[(13, 3), (7, 2), (10, 3), (12, 4), (20, 8), (6, 13)]

さて、容量やアイテムがなくなるまで、できるだけ価値のあるアイテムを手に入れましょう。

0. cap = 15, price = 0
1. Take (13, 3): cap = 12, price = 13
2. Take (7, 2): cap = 10, price = 20
3. Take (10, 3): cap = 7, price = 30
4. Take (12, 4): cap = 3, price = 42
5. Take (20, 8): cap = 0, price = 49.5
   [in this step, you have capacity to take 3 units, so take 3 units of the 5th item, the price of which is 3*20/8]

分数のアイテムを取得できない場合、そのような貪欲なアプローチでは最適なソリューションが得られない可能性があります。