【競技プログラミング】0-1ナップサック問題をやってみた【組合せ最適化】

1.初めに

・アルゴリズムを学ぶために、競技プログラミングを始めました。
・AOJのコースをやっていくので、その備忘録を残します。

・前回はコイン問題を解いたので、今回は「0-1ナップサック問題」を解いていきます。

2.0-1ナップサック問題

2.1問題

価値が vi 重さが wi であるような N 個の品物と、容量が W のナップザックがあります。次の条件を満たすように、品物を選んでナップザックに入れます。

・選んだ品物の価値の合計をできるだけ高くする。
・選んだ品物の重さの総和は W を超えない。

価値の合計の最大値を求めてください。

入力

１行目に２つの整数　N、W　が空白区切りで１行に与えられます。 続く N 行で i 番目の品物の価値 vi と重さ wi が空白区切りで与えられます。

出力

価値の合計の最大値を１行に出力してください。

制約

1 ≤ N ≤ 100
1 ≤ vi ≤ 1,000
1 ≤ wi ≤ 1,000
1 ≤ W ≤ 10,000

2.2.DPテーブルを作る

・まずはコイン問題でやったように、入力例を使って自力でDPテーブルを埋めてみましょう。

4 5
4 2
5 2
2 1
8 3

・入力例1が↑なので、これを元にDPテーブルを作っていきます。

i：品物の番号
j：容量の大きさ
として

$$\boldsymbol{dp[i][j]=i番目までの品物を使って、容量がjを超えないようなvの最大値}$$
としてdp表を埋めていきます。

・i=1、j=0の時

		i\j	0	1	2	3	4	5
vi↓	wi↓	0	0	0	0	0	0	0
4	2	1	次
5	2	2
2	1	3
8	3	4

・$dp[1][0]$ は1番目までの品物を使って容量0を超えないように価値を最大にしなきゃ。
　　　　　　　　　　　　↓
・１番目の品物って[価値=4、重さ=2]だなあ。
　　　　　　　　　　　　↓
・重さ(w)=2って既に容量(j)=0を超えてるから、品物使えないじゃん。
　　　　　　　　　　　　↓
・使える品物がないから、価値の最大値($dp[1][0]$ )は0だ！

		i\j	0	1	2	3	4	5
vi↓	wi↓	0	0	0	0	0	0	0
4	2	1	0
5	2	2
2	1	3
8	3	4

みたいな感じです。


・i=2、j=3の時

		i\j	0	1	2	3	4	5
vi↓	wi↓	0	0	0	0	0	0	0
4	2	1	0	0	4	4	4	4
5	2	2	0	0	次
2	1	3
8	3	4

・$dp[2][3]$ は2番目までの品物を使って容量3を超えないように価値を最大にしなきゃ。
　　　　　　　　　　　　↓
・2番目までの品物って[価値=4、重さ=2]、[価値=5、重さ=2]の二個だなあ。
　　　　　　　　　　　　↓
・[価値=5、重さ=2]を使えば価値が最大にできるなあ。
　　　　　　　　　　　　↓
・[価値=5、重さ=2]を使うから、価値の最大値($dp[2][3]$ )は5だ。

		i\j	0	1	2	3	4	5
vi↓	wi↓	0	0	0	0	0	0	0
4	2	1	0	0	4	4	4	4
5	2	2	0	0	5
2	1	3
8	3	4

みたいな感じです。


・自力で埋めるとこんな感じです。↓

		i\j	0	1	2	3	4	5
vi↓	wi↓	0	0	0	0	0	0	0
4	2	1	0	0	4	4	4	4
5	2	2	0	0	5	5	9	9
2	1	3	0	2	5	7	9	11
8	3	4	0	2	5	8	10	13

・$dp[i][j]$を埋める時にまず最初に考えるのが、「$j$と$w$の値を比較する」です。
　　　　　　　　　　　　↓
・次の①か②で場合分けをします。

①：「j<w」となる時(i番目の品物の重さ(w)がjの値を超えてしまっている時)

・その$i$番目の品物は使えない。(使っただけで、容量オーバーしてしまうから)
　　　　　　　　　　　　↓
・それまでの価値の最大値($dp[i-1][j]$)をそのまま$dp[i][j]$入れる。

・例)i=4、j=2の時：(4個目までの品物を使って容量2を超えないように価値の最大値を決めるとき)↓

②：「j≥w」となる時(①の逆の場合)

・$dp[i-1][j-w]+v$を計算する。
　　　　　　　　　　　　↓
・$dp[i-1][j-w]+v$と$dp[i-1][j]$を比べて、値の大きい方を$dp[i][j]$に入れる。

・例)i=3,j=5の時：(3個目までの品物を使って容量5を超えないように価値の最大値を決めるとき)

以下脳内の考え・・・
・3個目までの品物は[価値=4、重さ=2]、[価値=5、重さ=2]、[価値=2、重さ=1]の三個使えるなあ。
　　　　　　　　　　　　↓
・[価値=5、重さ=2]、[価値=5、重さ=2] (これってdp[i-1][j-w]の時と同じ組み合わせだよなあ)と[価値=8、重さ=3] (新しく使う品物)の三個の品物を使えば価値が最大=18(これが$dp[i-1][j-w]+v$)となる！

みたいな感じです。

・①、②を式で表すと

dp[i][j] = \left\{
\begin{array}{ll}
dp[i-1][j] & (j<w) \\
max(dp[i-1][j], dp[i-1 ][j-w]+v) & (otherwise)
\end{array}
\right.

となる。

2.3.DP表を一次元にして考える

0-1ナップサック問題のdpテーブルも一次元にできます。

コイン問題と違ってdp[i-1][j-w]+vはi-1行目の値から求めるのでで、コイン問題とは違い、jを大きい方から左方向へdp[i][j]を埋めていきます。

・例)i=3,j=3の時：(3個目までの品物を使って容量3を超えないように価値の最大値を決めるとき)

		i\j	0	1	2	3	4	5
vi↓	wi↓	0	0	0	0	0	0	0
4	2	1	0	0	4	4	4	4
5	2	2	0	0	5	5	9	9
2	1	3				次	9	11
8	3	4

・例えば上の表では、3行目をjの大きい方から逆向きに更新して、$dp[3][4]$ まで更新されています。

　　　↓

　　　　　　　↓
・次求めたい値(更新する値)が$dp[3][3]$だとします。
　　　　　　　↓
・$dp[3][3]=7$と分かりました。
　　　　　　　↓
・更新！！
　　　　　　　↓

vi↓	wi↓	i\j	0	1	2	3	4	5
2	1	3	0	0	5	7	9	11

・みたいな感じで埋めていきます。


・つまり、i番目までの品物を使い、容量jの時の価値の最大値は
$$
dp[j] = max(dp[j], dp[j-w]+v)
$$
と表すことができます。

2.3.1.実装(一次元バージョン)

# 入力値を取得
n,W=map(int,input().split())

# 一次元のdpテーブルを作る
dp=[0 for j in range(W+1)]

# v(価値)、w(重さ)を取得するために品物の個数をiとして回す
for i in range(n):
    v,w=map(int,input().split())
    
    # jを大きい方から逆に回す
    for j in range(W,w-1,-1):
        dp[j]=max(dp[j],dp[j-w]+v)
print(dp[W])

参考サイト