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

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

https://qiita.com/kindamu24005/private/3be5a55ce3c6c5275f4d

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

# 2.ナップサック問題


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


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

・選んだ品物の価値の合計をできるだけ高くする。
・選んだ品物の重さの総和は $W$ を超えない。
<font color="red">・同じ種類の品物はいくつでも選ぶことができる。</font>(この部分が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テーブルを作る
・<B>基本的には前回の0-1ナップサック問題と同じ考えです。</B>
```
4 8
4 2
5 2
2 1
8 3
```
・入力例1が↑なので、これを元にDPテーブルを作っていきます。

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

・とりあえず自力で埋めてみました。↓
|||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 |

<br>
<br>
<br>

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


### ②：その逆(j≥w)の場合は<font color="red"><B>(前回と違う！)</B></font>

・dp[<font color="red"><B>i</B></font>][j-w]+vを計算する。(前回はdp[<B>i-1</B>][j-w]+v)
　　　　　　　　　　　　↓
・dp[<font color="red"><B>i</B></font>][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の時：(<B>4個目までの品物</B>を使って<B>容量7を超えないように</B>価値の最大値を決めるとき)↓
|||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 |  |   |

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

みたいな感じです。



・①、②を式で表すと

```math
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表を一次元にして考える
:::note 
例によってナップサック問題のdpテーブルも一次元にできます。
:::
:::note alert
今度は<B>dp[i][j-w]+vを同じi行目の値から求めることができるの</B>で、0-1ナップサック問題とは違い、<B>jを0から右方向</B>へdp[i][j]を埋めていきます。
:::
・例)i=4,j=7の時：(<B>4個目までの品物</B>を使って<B>容量7を超えないように</B>価値の最大値を決めるとき)↓
|||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 | <B>次</B> |   |

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

|vi↓|wi↓| <B>i\j</B>  |0  |1  |2  |3  |4  |5  |6  |7  |8  |
---|---|---|---|---|---|---|---|---|---|---|---|
|8|3|**4**  | 0 | 2 | 5 | 8 | 10 | 13 | 16 | <B>次</B> | 20 | 

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


|vi↓|wi↓| <B>i\j</B>  |0  |1  |2  |3  |4  |5  |6  |7  |8  |
---|---|---|---|---|---|---|---|---|---|---|---|
|8|3|**4**  | 0 | 2 | 5 | 8 | 10 | 13 | 16 | <font color="red"><B>18</B></font> | 20 | 

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

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