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

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

https://qiita.com/kindamu24005/private/e2990a1df48f40502b81

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

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


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

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

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

価値の合計の最大値を求めてください。
### 入力
１行目に２つの整数　$N$、$W$　が空白区切りで１行に与えられます。 続く $N$ 行で $i$ 番目の品物の価値 $v_i$ と重さ $w_i$ が空白区切りで与えられます。
### 出力
価値の合計の最大値を１行に出力してください。
### 制約
$1 ≤ N ≤ 100$
$1 ≤ v_i ≤ 100$
$1 ≤ w_i ≤ 10,000,000$ <B>←?!</B>
$1 ≤ W ≤ 1,000,000,000$ <B>←?!</B>

## 2.1.1.0-1ナップサック問題との違い
・**各品物の重さ**$w$と**ナップサックの容量**$W$の**制約**が**桁違いに大きく**なっています。
　　　　　　　　　　　　↓　そうすると、、、
・DPテーブルの$j$を**ナップサックの容量**として作ると、<font color="red"><B>計算量がヤバい</B></font>ことになります。
　　　　　　　　　　　　↓　じゃあどうするか

:::note info
**j**を**価値の大きさ**として考えます！！
:::
## 2.2.DPテーブルを作る
・上で説明したように、DPテーブルの$j$を**ナップサックの容量**として作ると、<font color="red"><B>計算量がヤバい</B></font>ことになるので、以下のようにしてDPテーブルを作成していきます。

:::note
i：品物の番号
<font color="red"><B>j：価値の大きさ</B></font>
として

$$\boldsymbol{dp[i][j]=i番目までの品物を使って、jの価値を出すための最小の重さ}$$
としてdp表を埋めていきます。
:::
・$1 ≤ N ≤ 100$、$1 ≤ v_i ≤ 100$　なので、「$j$の最大値$=$最大計算量$=10,000$」となって、「$1 ≤ W ≤ 1,000,000,000$ 」を$j$にして計算をするよりはマシ、ということですね！！
<br>

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


・i=1、j=0の時
(最初、全部のdp[i][j]には「inf」が入っていますが、見にくいので省略しています。)
|||i\j  |0  |1  |2  |3  |4  |5  |6 |7|8|
---|---|---|---|---|---|---|---|---|---|---|---|
|vi↓|wi↓|**0**  | inf | inf | inf | inf | inf | inf |inf | inf |...|
|4|2|**1**  | <B>次</B> |  |  |  |  |  |
|5|2|**2**  |  |  |  |  |  |  |
|2|1|**3**  |  |  |  |  |  |  |
|8|3|**4**  |  |  |  |  |  |  |

・$dp[1][0]$ は**1番目までの品物**を使って**価値0**を出すための最小の重さはなんだ？
　　　　　　　　　　　　↓
・１番目の品物って<B>[価値=4、重さ=2]</B>だなあ。
　　　　　　　　　　　　↓
・<B>1番目の品物の価値(w)=4って既に予定の価値(j)=0を超えてる</B>から、品物使えないじゃん。
　　　　　　　　　　　　↓
・使える品物がないから、最小の重さ($dp[1][0]$ )は**0**だ！
|||i\j  |0  |1  |2  |3  |4  |5  |6 |7|8|...|
---|---|---|---|---|---|---|---|---|---|---|---|---|
|vi↓|wi↓|**0**  | 0 | inf | inf | inf | inf | inf |inf | inf | inf |...|
|4|2|**1**  | <B>0</B> |  | | | | | |||...|
|5|2|**2**  |  |  |  |  |  |  |
|2|1|**3**  |  |  |  |  |  |  |
|8|3|**4**  |  |  |  |  |  |  |

みたいな感じです。
<br>
・i=2、j=4の時
|||i\j  |0  |1  |2  |3  |4  |5  |6 |7|8|...|
---|---|---|---|---|---|---|---|---|---|---|---|---|
|vi↓|wi↓|**0**  | inf | inf | inf | inf | inf | inf |inf | inf | inf |...|
|4|2|**1**  | 0 | inf |inf |inf |inf|inf |inf |inf|inf|...|
|5|2|**2**  | 0 |inf  |inf|inf|<B>次</B>|  |
|2|1|**3**  |  |  |  |  |  |  |
|8|3|**4**  |  |  |  |  |  |  |

・$dp[2][4]$ は**2番目までの品物**を使って**価値4**を出すための最小の重さはなんだ？
　　　　　　　　　　　　↓
・2番目までの品物って<B>[価値=4、重さ=2]、[価値=5、重さ=2]</B>の二個だなあ。
　　　　　　　　　　　　↓
・<B>[価値=4、重さ=2]</B>はを使えば価値を4にして、重さを最小にできるなあ。
　　　　　　　　　　　　↓
・<B>[価値=4、重さ=2]</B>を使うから、最小の重さ($dp[2][3]$ )は**2**だ。


|||i\j  |0  |1  |2  |3  |4  |5  |6 |7|8|...|
---|---|---|---|---|---|---|---|---|---|---|---|---|
|vi↓|wi↓|**0**  | 0 | inf | inf | inf | inf | inf |inf | inf | inf |...|
|4|2|**1**  | 0 | inf |inf |inf |2|inf |inf |inf|inf|...|
|5|2|**2**  | 0 | inf |inf  |inf  | <B>2</B>| 
|2|1|**3**  |  |  |  |  |  |  |
|8|3|**4**  |  |  |  |  |  |  |


みたいな感じです。

:::note warn
(i番目までの品物を使って**jの価値をピッタリ出せない**ところは**inf**となってます。)
:::
<br>

・自力で埋めるたいところですが、jは$10,000$まであるので、「...」のところまで埋めるのは流石に無理でした。↓
|||i\j  |0  |1  |2  |3  |4  |5  |6 |7|8|...|
---|---|---|---|---|---|---|---|---|---|---|---|---|
|vi↓|wi↓|**0**  | 0 | inf | inf | inf | inf | inf |inf | inf | inf |...|
|4|2|**1**  | 0 | inf |inf |inf |2|inf |inf |inf|inf|...|
|5|2|**2**  | 0 | inf |inf  |inf | 2|2|inf|inf|inf|...| 
|2|1|**3**  | 0 | inf | 1 | inf | 2 | 2 |3|3|inf|...|
|8|3|**4**  | 0 | inf | 1 | inf | 2 | 2 |3|3|3|...|
<br>
<br>
<br>

<B>・$dp[i][j]$を埋める時にまず最初に考えるのが、「$j$と<font color="red"> $v$ </font>の値を比較する」です。
　　　　　　　　　　　　↓
・次の①か②で場合分けをします。

### ①：「j<v」となる時(i番目の品物の価値(v)がjの値を超えてしまっている時) 
・その$i$番目の品物は**使えない。**(使っただけで、価値がオーバーしてしまうから)
　　　　　　　　　　　　↓
・それまでの価値の最大値($dp[i-1][j]$)をそのまま$dp[i][j]$入れる。

・例)i=4、j=2の時：(<B>4個目までの品物</B>を使って<B>価値が2</B>となるような重さの最小値を決めるとき)↓
![0-1ナップサックⅡ.001.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/33da7f07-49c4-1ddb-0bd6-1b0482902674.jpeg)


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

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

・例)i=3,j=6の時：(<B>3個目までの品物</B>を使って<B>価値が6</B>となるような、重さの最小値を決めるとき)
![0-1ナップサックⅡ.002.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/c85929bf-2b12-1c31-339e-0dea29b8c037.jpeg)



・①、②を式で表すと　

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

となる。

## 2.3.実装
```python
N,W=map(int,input().split())

# dp表を作る
inf = float("inf")
# 10000+1はjの限界値
dp=[[inf for j in range(10000+1)] for i in range(N+1)]

# 初期値設定
dp[0][0]=0

# dp表を埋めていく
for i in range(1,N+1):
  v,w=map(int,input().split())
  for j in range(10000+1):
    if j<v:
      dp[i][j]=dp[i-1][j]
    else:
      dp[i][j]=min(dp[i-1][j],dp[i-1][j-v]+w)

# 求めたいのは「選んだ品物の重さの合計値(dp[i][j])が容量Wを超えない時の価値(j)の最大値」→条件に当てはまるjを見つける
for j in range(10000,0,-1):
  if dp[N][j]<=W:
    print(j)
    exit()

# 条件を満たす時がない(品物を一つも使えない時)は0を出力
print(0)
```

## 2.4.DP表を一次元にして考える
:::note 
0-1ナップサック問題Ⅱのdpテーブルも一次元にできます。
:::

:::note warn
0-1ナップサック問題と同じで、<B>dp[i-1][j-v]+wはi-1行目の値から求めるので</B>で、<B>jを大きい方から左方向</B>へdp[i][j]を埋めていきます。(二次元配列の時は右方向からでOK)
:::

![0-1ナップサックⅡ.003.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/245742df-7b03-38ea-d386-99eb2d69812b.jpeg)
![0-1ナップサックⅡ.004.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/72ee8ece-5461-0628-bd6c-d58863bccff9.jpeg)


・例)i=3,j=6の時：(<B>3個目までの品物</B>を使って<B>価値が3</B>となるような、重さの最小値を決めるとき)
|||i\j  |0  |1  |2  |3  |4  |5  |6 |7|8|...|
---|---|---|---|---|---|---|---|---|---|---|---|---|
|vi↓|wi↓|**0**  | 0 | inf | inf | inf | inf | inf |inf | inf | inf |...|
|4|2|**1**  | 0 | inf |inf |inf |2|inf |inf |inf|inf|...|
|5|2|**2**  | 0 | inf |inf  |inf | 2|2|inf|inf|inf|...| 
|2|1|**3**  |  |  |  |  |  |  |**次**|3|inf|...|
|8|3|**4**  |  | | | | | ||||...|
<br>
<br>
・例えば上の表では、<B>3行目をjの大きい方から逆向きに更新して</B>、$dp[3][7]$ まで更新されています。

  　　　↓
![0-1ナップサックⅡ.005.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/6488e059-ea70-4968-c8dd-c0befb0cf59d.jpeg)
　　　　　　　↓
・次求めたい値(更新する値)が$dp[3][6]$だとします。
　　　　　　　↓
・$dp[3][6]=3$と分かりました。
　　　　　　　↓
・更新！！
　　　　　　　↓


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



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

# DP表（一次元）を作る
inf = float("inf")
dp=[inf]*(10000+1)
dp[0]=0

# dp[i][j]を埋めていく
for i in range(N):
    v,w=map(int,input().split())

    # 逆から回す
    for j in range(10000,v-1,-1):
        dp[j]=min(dp[j],dp[j-v]+w)

# 求めたいのは「選んだ品物の重さの合計値(dp[i][j])が容量Wを超えない時の価値(j)の最大値」→条件に当てはまるjを見つける
for j in range(10000,0,-1):
    if dp[j]<=W:
        print(j)
        exit()

# 条件を満たす時がない(品物を一つも使えない時)は0を出力
print(0)
```