ナップザック問題

knapsack.png

いくつかの品物があり、
その品物にはそれぞれ

  • 重量
  • 価値

の2つのパラメータが与えられている。
ある一定の重さまで品物を運べるとしたときに、
価値の合計の最大値はいくつになるか?

重さは合計10運べるとする。
品物 A B C D E
重量 3 4 1 2 3
価値 2 3 2 3 6

ああ、PS3のゲームのスカイリムでも同じ問題に直面するよ。
限られた運べる重量の中で、いかに価値のあるものを選んで運ぶか、って。あれの場合、武器は外せないけど。

方針

  • 一つ一つに対して「買う」「買わない」を選ぶ(メモする)
  • 持てる重さが超えていないものの中で最大のものを探索する

単純に深さ優先全探索した場合

すべての荷物に対して、「買う」「買わない」の2つの分岐で進んでいった木です。
ノードは現在の重量と金額を記した状態です。
knapsack.svg
ソースコード
これには無駄な探索がたくさんあります。同じ状態に何回もなったりしてますね

メモを使って無駄な探索をなくす

* 横軸…..何番目の品物まで考えたか

  • 縦軸…..合計の重さ
  • 値….価値の合計の最大値
Status[][] mMemo=new Status[mItemNum+1][mLimit+1];

ソースコード
さっきのと比べて無駄な探索が減った分、矢印の数が減ってますね
knapsack_memo.svg
メモは最終的にこのようになります
A(3,2) B(4,3) C(1,2) D(2,3) E(3,6)
0 10,14 10,14 6,11 5,9 3,6
1 5,9 3,6
2 3,6
3 10,13 6,11 5,9 3,6
4 6,11 5,9 3,6
5 5,9 3,6
6 3,6
7 6,10 5,8 3,6
8 5,8 3,5
9 3,5
10 3,5

空欄部分は存在しない組み合わせです。

まとめ

可能な限り引数が減るような再帰関数を作ろう

for文で解く!動的計画法の解き方

  • 縦軸は累積した荷物の重さ
  • 横軸はこの買った商品場合
  • 値は現在の累積価値
を示しています。
まず、初期状態から品物A(重さ=3,価値=2)を買ったとすると、動的計画法の配列はこうなります
初期状態 A,3,2 B,4,3 C,1,2 D,2,3 E,3,6
0 0
1
2
3 2
次、は初期状態から商品B(重さ=4,値=3)を買った場合を示しています
初期状態 A,3,2 B,4,3 C,1,2 D,2,3 E,3,6
0 0 0
1
2
3 2
4 3
同様に、初期状態からC,D,Eを買った状態まで進めるとこんなかんじになります
初期状態 A,3,2 B,4,3 C,1,2 D,2,3 E,3,6
0 0 0 0 0 0
1 2
2 3
3 2 6
4 3
次の配列、Aの列の4行目に価値2が増えました。これは何を示しているのでしょう?
初期状態 A,3,2 B,4,3 C,1,2 D,2,3 E,3,6
0 0 0 0 0 0
1 0 2
2 3
3 2 6
4 2 3
現在の合計重さが1,価値=0の状態で、Aを買った場合,重さ4,価値2 の状態になりますよ、という意味です。
こんな組み合わせありえないですね。
ありえないですが、今後あった場合のときのためにとりあえずメモしていきます。
初期状態 A,3,2 B,4,3 C,1,2 D,2,3 E,3,6
0 0 0 0 0 0
1 0 0 0 2
2 2 3
3 2 6
4 2 3
5 3
3,1->4,3 +w=2
初期状態 A,3,2 B,4,3 C,1,2 D,2,3 E,3,6
0 0 0 0 0 0
1 0 0 0 2
2 2 3
3 2 5 6
4 2 3
5 3
全部走査していくと、最終的に配列はこうなります
初期状態 A,3,2 B,4,3 C,1,2 D,2,3 E,3,6
0 0 0 0 0 0
1 0 0 0 2 0
2 0 0 0 2 3
3 0 2 0 2 5 6
4 0 2 3 2 5 6
5 0 2 3 5 5 9
6 0 2 3 5 5 11
7 0 2 5 5 8 11
8 2 5 7 8 11
9 2 5 7 8 11
10 2 5 7 10 14

ナップザック問題についての記述がある本


depth-first-search

サポートサイト Wikidot.com depth-first-search