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

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

https://qiita.com/kindamu24005/items/6177591141a146cc0d9d

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

# 2.0-1ナップサック問題


https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/1/DPL_1_B


## 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テーブルを作る
・まずはコイン問題でやったように、入力例を使って自力で<B>DPテーブル</B>を埋めてみましょう。
```
4 5
4 2
5 2
2 1
8 3
```
・入力例1が↑なので、これを元にDPテーブルを作っていきます。

:::note
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**  | <B>次</B> |  |  |  |  |  |
|5|2|**2**  |  |  |  |  |  |  |
|2|1|**3**  |  |  |  |  |  |  |
|8|3|**4**  |  |  |  |  |  |  |

・$dp[1][0]$ は**1番目までの品物**を使って**容量0**を超えないように価値を最大にしなきゃ。
　　　　　　　　　　　　↓
・１番目の品物って<B>[価値=4、重さ=2]</B>だなあ。
　　　　　　　　　　　　↓
・<B>重さ(w)=2って既に容量(j)=0を超えてる</B>から、品物使えないじゃん。
　　　　　　　　　　　　↓
・使える品物がないから、価値の最大値($dp[1][0]$ )は**0**だ！
|||i\j  |0  |1  |2  |3  |4  |5  |
---|---|---|---|---|---|---|---|---|
|vi↓|wi↓|**0**  | 0 | 0 | 0 | 0 | 0 | 0 |
|4|2|**1**  | <font color="red"><B>0</B></font> |  |  |  |  |  |
|5|2|**2**  |  |  |  |  |  |  |
|2|1|**3**  |  |  |  |  |  |  |
|8|3|**4**  |  |  |  |  |  |  |

みたいな感じです。
<br>
・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 | <B>次</B> |  |  |  |
|2|1|**3**  |  |  |  |  |  |  |
|8|3|**4**  |  |  |  |  |  |  |

・$dp[2][3]$ は**2番目までの品物**を使って**容量3**を超えないように価値を最大にしなきゃ。
　　　　　　　　　　　　↓
・2番目までの品物って<B>[価値=4、重さ=2]、[価値=5、重さ=2]</B>の二個だなあ。
　　　　　　　　　　　　↓
・<B>[価値=5、重さ=2]</B>を使えば価値が最大にできるなあ。
　　　　　　　　　　　　↓
・<B>[価値=5、重さ=2]</B>を使うから、価値の最大値($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 | <font color="red"><B>5</B></font> |  |  |  |
|2|1|**3**  |  |  |  |  |  |  |
|8|3|**4**  |  |  |  |  |  |  |

みたいな感じです。
<br>
・自力で埋めるとこんな感じです。↓
|||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 |

<br>
<br>
<br>

<B>・$dp[i][j]$を埋める時にまず最初に考えるのが、「$j$と$w$の値を比較する」です。
　　　　　　　　　　　　↓
・次の①か②で場合分けをします。
### ①：「j<w」となる時(i番目の品物の重さ(w)がjの値を超えてしまっている時) 
・その$i$番目の品物は**使えない。**(使っただけで、容量オーバーしてしまうから)
　　　　　　　　　　　　↓
・それまでの価値の最大値($dp[i-1][j]$)をそのまま$dp[i][j]$入れる。

・例)i=4、j=2の時：(<B>4個目までの品物</B>を使って<B>容量2を超えないように</B>価値の最大値を決めるとき)↓
![名称未設定.001.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/17fc84a4-cad6-090b-88f8-0ef00a0fdc68.jpeg)

### ②：「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の時：(<B>3個目までの品物</B>を使って<B>容量5を超えないように</B>価値の最大値を決めるとき)
![名称未設定.001.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/5c7f1cb0-b919-a05a-6ef7-038231b7d56e.jpeg)
以下脳内の考え・・・
・<B>3個目までの品物</B>は<B>[価値=4、重さ=2]、[価値=5、重さ=2]、[価値=2、重さ=1]</B>の三個使えるなあ。
　　　　　　　　　　　　↓
・<B>[価値=5、重さ=2]、[価値=5、重さ=2] <font color="blue">(これってdp[i-1][j-w]の時と同じ組み合わせだよなあ)</font></B>と<B>[価値=8、重さ=3] (新しく使う品物)</B>の三個の品物を使えば<B>価値が最大=18</B>(これが$dp[i-1][j-w]+v$)となる！

みたいな感じです。



・①、②を式で表すと

```math
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表を一次元にして考える
:::note 
0-1ナップサック問題のdpテーブルも一次元にできます。
:::
:::note alert
コイン問題と違って<B>dp[i-1][j-w]+vはi-1行目の値から求めるので</B>で、コイン問題とは違い、<B>jを大きい方から左方向</B>へdp[i][j]を埋めていきます。
:::
![名称未設定.003.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/8e529d97-207a-ea91-8bb2-80af57218bbd.jpeg)
![名称未設定.004.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/a270142a-eaf2-9519-5f3b-2a49581256c8.jpeg)



・例)i=3,j=3の時：(<B>3個目までの品物</B>を使って<B>容量3を超えないように</B>価値の最大値を決めるとき)
|||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**  |  |  |  | <B>次</B> | 9 | 11 |
|8|3|**4**  |  |  |  |  |  |  |

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

  　　　↓
![名称未設定.005.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/b07975c6-2726-8c61-167e-abb08f46bc0f.jpeg)
　　　　　　　↓
・次求めたい値(更新する値)が$dp[3][3]$だとします。
　　　　　　　↓
・$dp[3][3]=7$と分かりました。
　　　　　　　↓
・更新！！
　　　　　　　↓


|vi↓|wi↓|i\j  |0  |1  |2  |3  |4  |5  |
---|---|---|---|---|---|---|---|---|
|2|1|**3**  | 0 | 0 | 5 | <font color="red"><B>7</B></font> | 9 | 11 |

・みたいな感じで埋めていきます。
<br>
・つまり、i番目までの品物を使い、容量jの時の価値の最大値は
$$
dp[j] = max(dp[j], dp[j-w]+v)
$$
と表すことができます。
## 2.3.1.実装(一次元バージョン)
```python
# 入力値を取得
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])
```

# 参考サイト

https://o-treetree.hatenablog.com/archive/category/AOJ