ナップザック問題解き方
0 likes
1Answer
$B=35$で横軸35まで書くのは ダルい 見た目が分かりづらいので、下記の商品を重さ10まで入れる場合のナップサック問題についてDP表を書いてみます。
| i | 重さ$w_i$ | 価値$p_i$ |
|---|---|---|
| 1 | 3 | 1 |
| 2 | 5 | 4 |
| 3 | 3 | 2 |
| 4 | 2 | 1 |
| 5 | 3 | 1 |
| 6 | 2 | 1 |
| 7 | 4 | 3 |
| 8 | 4 | 2 |
まず、ナップサック問題でのDP表は、縦軸$i$は「商品をいくつまでナップサックに入れるか」で、横軸$w$は「荷物の総重量」になります。
で、表の項目に記入するのは、その重さ以下で「最大の価値」を記入することになります。
横軸は重さなので、今回の最大重量である10の欄まで記入します。最大重量が35なら0~35の欄までになります。
まず、１つも商品を入れない$i=0$の場合の表は当然下記のようになります。
何も入れてないんですから、価値は全部$0$です。
全部$0$で埋めてください。
| i＼w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 重さ$w_i$ | 価値$p_i$ |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
では、商品1の行($i=1$)を埋めます。
上の行で入れる商品の重さ($w_1=3$)分だけ左の列の値に商品の価値($p_1=1$)を足した数と、上の行の数の大きい方を空欄へ埋めていきます。
左の列が表の外に出てしまう場合は上の列の数字をそのまま書きます。
今回の例であれば、$w$が0〜2の欄は0になります。
| i＼w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 重さ$w_i$ | 価値$p_i$ |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ||
| 1 | 0 | 0 | 0 | 3 | 1 |
そして、$w$が3以上の欄は、3つ左の欄が0で、上の数字は0ですので、全部1になります。
| i＼w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 重さ$w_i$ | 価値$p_i$ |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ||
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 3 | 1 |
次に$i=2$の列を考えます。
商品2は重さが$w_2=5$で価値が$p_2=4$ですので、上の欄の5列左の数字に4を足した数と直上の数を比べて大きい数字を書いていきます。
まず、左に５列行ったら表の外に行ってしまう0~4までを上と同じ数字にします。
| i＼w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 重さ$w_i$ | 価値$p_i$ |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ||
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 3 | 1 |
| 2 | 0 | 0 | 0 | 1 | 1 | 5 | 4 |
$w=5$より右は、一個上の列で5個左の数に4を足した数字と上の数字を見比べて大きい方を書き込んでいきます。
$w=5$なら、$0+4$と$1$を見比べて4になります。
$w=8$なら、$1+4$と$1$なので5ですね。
| i＼w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 重さ$w_i$ | 価値$p_i$ |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ||
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 3 | 1 |
| 2 | 0 | 0 | 0 | 1 | 1 | 4 | 4 | 4 | 5 | 5 | 5 | 5 | 4 |
$i=3$の列でもやってみましょう。
商品3は重さが$w_3=3$で価値が$p_3=2$ですので、一個上の欄の3列左の数字に2を足した数と直上の数を比べて大きい数字を書いていきます。
まず、左に3列行ったら表の外に行ってしまう0~2までを上と同じ数字にします。
| i＼w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 重さ$w_i$ | 価値$p_i$ |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ||
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 3 | 1 |
| 2 | 0 | 0 | 0 | 1 | 1 | 4 | 4 | 4 | 5 | 5 | 5 | 5 | 4 |
| 3 | 0 | 0 | 0 | 3 | 2 |
$w=3$なら、$0+2$と$1$を見比べて2になります。
$w=6$なら、$1+2$と$4$なので4です。
$w=8$なら、$4+2$と$5$なので6ですね。
| i＼w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 重さ$w_i$ | 価値$p_i$ |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ||
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 3 | 1 |
| 2 | 0 | 0 | 0 | 1 | 1 | 4 | 4 | 4 | 5 | 5 | 5 | 5 | 4 |
| 3 | 0 | 0 | 0 | 2 | 2 | 4 | 4 | 4 | 6 | 6 | 6 | 3 | 2 |
上の手順を$i=8$まで繰り返すと下記のようなDP表になります。
| i＼w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 重さ$w_i$ | 価値$p_i$ |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ||
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 3 | 1 |
| 2 | 0 | 0 | 0 | 1 | 1 | 4 | 4 | 4 | 5 | 5 | 5 | 5 | 4 |
| 3 | 0 | 0 | 0 | 2 | 2 | 4 | 4 | 4 | 6 | 6 | 6 | 3 | 2 |
| 4 | 0 | 0 | 1 | 2 | 2 | 4 | 4 | 5 | 6 | 6 | 7 | 2 | 1 |
| 5 | 0 | 0 | 1 | 2 | 2 | 4 | 4 | 5 | 6 | 6 | 7 | 3 | 1 |
| 6 | 0 | 0 | 1 | 2 | 2 | 4 | 4 | 5 | 6 | 6 | 7 | 2 | 1 |
| 7 | 0 | 0 | 1 | 2 | 3 | 4 | 4 | 5 | 6 | 7 | 7 | 4 | 3 |
| 8 | 0 | 0 | 1 | 2 | 3 | 4 | 4 | 5 | 6 | 7 | 7 | 4 | 2 |
$i=8$,$w=10$の数値が答えになるので、重量10まで商品を詰めた時の価値の最大値は7になります。
総当たりで解けば、商品2,商品3,商品4で合計重量($5+3+2=10$)、合計価値($4+2+1=7$)になりますので、ちゃんと解けています。
0Like