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

1.初めに

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

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

2.ナップサック問題

2.1問題

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

・選んだ品物の価値の合計をできるだけ高くする。
・選んだ品物の重さの総和は $W$ を超えない。
・同じ種類の品物はいくつでも選ぶことができる。(この部分が0-1ナップサックと違う！！！！！！！！)

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

入力

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

出力

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

制約

$1 ≤ N ≤ 100$
$1 ≤ v_i ≤ 1,000$
$1 ≤ w_i ≤ 1,000$
$1 ≤ W ≤ 10,000$

2.2.DPテーブルを作る

・基本的には前回の0-1ナップサック問題と同じ考えです。

4 8
4 2
5 2
2 1
8 3

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

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

・とりあえず自力で埋めてみました。↓

		i\j	0	1	2	3	4	5	6	7	8
vi↓	wi↓	0	0	0	0	0	0	0	0	0	0
4	2	1	0	0	4	4	8	8	12	12	16
5	2	2	0	0	5	5	10	10	15	15	20
2	1	3	0	2	5	7	10	12	15	17	20
8	3	4	0	2	5	8	10	13	16	18	21

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

①：i番目の品物の重さ(w)がjの値を超えてしまっていたら(j<w)

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

②：その逆(j≥w)の場合は(前回と違う！)

・dp[i][j-w]+vを計算する。(前回はdp[i-1][j-w]+v)
　　　　　　　　　　　　↓
・dp[i][j-w]+vとdp[i-1][j]を比べて、値の大きい方をdp[i][j]に入れる。
・つまりdp[i][j]に必要なdp[i][j-w]をi行目から得ることができる！！！（0-1の時はi-1行目から）

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

		i\j	0	1	2	3	4	5	6	7	8
vi↓	wi↓	0	0	0	0	0	0	0	0	0	0
4	2	1	0	0	4	4	8	8	12	12	16
5	2	2	0	0	5	5	10	10	15	15	20
2	1	3	0	2	5	7	10	12	15	17	20
8	3	4	0	2	5	8	10	13	16

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

みたいな感じです。

・①、②を式で表すと

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

となる。

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

例によってナップサック問題のdpテーブルも一次元にできます。

今度はdp[i][j-w]+vを同じi行目の値から求めることができるので、0-1ナップサック問題とは違い、jを0から右方向へdp[i][j]を埋めていきます。

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

		i\j	0	1	2	3	4	5	6	7	8
vi↓	wi↓	0	0	0	0	0	0	0	0	0	0
4	2	1	0	0	4	4	8	8	12	12	16
5	2	2	0	0	5	5	10	10	15	15	20
2	1	3	0	2	5	7	10	12	15	17	20
8	3	4	0	2	5	8	10	13	16	次

・例えば上の表では、4行目をjの小さい方から更新して、$dp[4][6]$まで更新されています。 　　　↓

vi↓	wi↓	i\j	0	1	2	3	4	5	6	7	8
8	3	4	0	2	5	8	10	13	16	次	20

　　　　　　　↓
・次求めたい値(更新する値)が$dp[4][7]$だとします。
　　　　　　　↓
・$dp[4][7]=18$と分かりました。( $dp[j-w]=10$で$v=8$より)
　　　　　　　↓
・更新！！
　　　　　　　↓

vi↓	wi↓	i\j	0	1	2	3	4	5	6	7	8
8	3	4	0	2	5	8	10	13	16	18	20

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


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

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

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

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

# v(価値)、w(重さ)を取得するために品物の個数をiとして回す
for i in range(n):
    v,w=map(int,input().split())

    # jを小きい方から逆に回す(0-1と逆)
    for j in range(w,W+1):
        dp[j]=max(dp[j],dp[j-w]+v)
print(dp[W])

参考サイト