ナップサック問題（再帰関数）

ナップサック問題

次のような問題を考えます。

[問題]

Ｎ個の品物があります。

それぞれの品物の 重さ(weight) と 価値(value) は分かっています。

これらの品物からいくつか選んでナップサックに詰めていきます。

ナップサックに入れる品物の 重さの総和 は capacity を超えてはいけません。

選んだ品物の 価値の総和 として考えられる最大値を求めて下さい。

解法・ソースコード

それぞれの品物を入れるか入れないかで分類しながら、再帰関数を使って探索を行ってみます。

再帰関数の第１引数には 品物のインデックス を渡し、第２引数には あとどのくらいの許容量があるか（どのくらいの重さを許容できるか） を渡し、返す値は 価値 となります。

再帰関数内の条件分としては次の３つになります。

  • 品物がない場合
    価値が増えないので 0 を返す。
  • 許容の重さを超える場合
    今回の品物は選択せずに、次の品物のチェックのため品物のインデックスを増やし関数をコールします。（再帰呼び出し）
    その関数の結果を返値（価値）とします。
  • 許容の重さを超えない場合
    今回の品物を 入れない場合 と 入れる場合 の両方で、次の品物のチェックのため品物のインデックスを増やし関数をコールします。（再帰呼び出し）
    ２つのパターンで価値の大きいほうを返値（価値）とします。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#---------- 入力例 ----------
items = [{'weight':2, 'value':3},
         {'weight':1, 'value':2},
         {'weight':3, 'value':4},
         {'weight':2, 'value':2}]
capacity = 5
#----------------------------
# i番目以降の品物の中から重さの総和がj以下となるように選ぶ
def rec(i, j):
    if i == len(items):  # 品物がもう残っていない場合
        res = 0
    elif j < items[i]['weight']:    # 品物が入らない場合
        res = rec(i + 1, j)
    else:
        # 品物を入れない場合と入れる場合で価値が大きいほうを選ぶ
        res = max(rec(i + 1, j), rec(i + 1, j - items[i]['weight']) + items[i]['value'])
    return res

print(rec(0, capacity))

[実行結果]

7

解（価値の総和の最大値）は 7 となりました。

１番目、２番目、４番目の品物を選んだ場合、価値の総和が7、重さの総和が5 となり 重さの許容範囲内で価値が最大 となっていることを確認できます。