こんにちは、皆さん。
この記事では、ナップザック問題を説明しようと思っています。
この問題は、面接の際、どこかで遭遇することでしょう。
この問題を解くために再帰的アプローチを使用します。
もし、再帰がどのように機能するか知らないのであれば、以下のチュートリアルを見てください。
Recursionについてもっと読む。
第1話 ナップザック問題入門
総重量 capacity を入れることができるナップザックを持っている泥棒がいる．彼は，重さと値段が異なるn個の品物をその場所から盗むことができる．
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
def knapsack(n,capacity,weights,prices):
if(n==0 or capacity==0):
return 0
if (weights[n-1]>capacity):
return knapsack(n-1,capacity,weights,prices)
else:
return max(prices[n-1] + knapsack(n-1,capacity-weights[n-1],weights,prices),
knapsack(n-1,capacity,weights,prices))
weights = [1,2,3,4]
prices = [50,200,150,100]
n = 4
capacity = 7
print(knapsack(n,capacity,weights,prices))
|
我々の目的は、すべての品物の重さの合計がナップザックに与えられた capacity を超えないことを考慮して、泥棒にとって最大の利益をもたらすこれらの品物の部分集合を見つける knapsack という関数を作成することです。
こちらもお読みください。
同じことを下の画像で説明しています。
再帰を用いたPythonによるナップザック問題の解法
各アイテムについて、泥棒は2つの選択肢を持っていると考えることにします。
その品物を入れるか、その品物を除いて拾わないかです。
もし泥棒が品物を入れたら、残りのn-1個の品物について最大利益を求め、また入れた品物の重さだけ容量を減らすことになる。
この場合の総利益は、「品物の値段＋残った（容量-品物の重さ）に対するn-1個の品物での利益」となります。
また、品物を除いた場合は、その店の残りのn-1個の品物の利益を求めればよいことになります。
この場合の利益は、次のようになります。
最終的な答えは、両方の場合の最大利益となる。
コード実装
現在のコードの実行後に受け取った出力は、正しい出力である400となった。
チュートリアルを読んでいただき、ありがとうございました。
ナップザック問題が理解できたと思います。
それでは、よい学習を