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

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

https://qiita.com/kindamu24005/private/12cb3b84cb7a57167c8b

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

# 2.個数制限付きナップサック問題

https://onlinejudge.u-aizu.ac.jp/problems/DPL_1_G

## 2.1問題
価値が $v_i$ 重さが $w_i$ であるような $N$ 種類の品物と、容量が $W$ のナップザックがあります。

次の条件を満たすように、品物を選んでナップザックに入れます：

・選んだ品物の価値の合計をできるだけ高くする。
・選んだ品物の重さの総和は $W$ を超えない。
・$i$ 番目の品物は $m_i$ 個まで選ぶことができる。<B>←New!!</B>

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

### 2.1.1.ナップサック問題との違い
・ナップサック問題では、同じ種類の品物を何個でも使ってよかったですが、この問題では文字通り<B>各品物ごとに使っていい個数が決められています。</B>

### 2.1.2.考え方
・入力例
```
4 8
4 3 2
2 1 1
1 2 4
3 2 2
```

・上の入力例を使って、DPテーブルの枠組みを↓のようにしてみます。(いつものDPテーブルに$m_i$が追加されています!!)

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

・まず考えられるのが、<B>「使っていい品物の個数をバラけさせて、各品物で入れるか入れないか(0-1ナップサック問題)をすれば解決じゃない？」</B>と思いつきます。

・つまり↓のようなDPテーブルです。(各iの品物について入れるか入れないかを考える)

||||i\j  |0  |1  |2  |3  |4  |5  |6 |7|8|
---|---|---|---|---|---|---|---|---|---|---|---|---|
|vi↓|wi↓|mi↓| **0** |  |  |  |  | |  | |  ||
|4|3|×|**1**  |  |  |  |  |  |  |
|4|3|×|**2**  |  |  |  |  |  |  |
|2|1|×|**3**  |  |  |  |  |  |  |
|1|2|×|**4**  |  |  |  |  |  |  |
|1|2|×|**5**  |  |  |  |  |  |  |
|1|2|×|**6**  |  |  |  |  |  |  |
|1|2|×|**7**  |  |  |  |  |  |  |
|3|2|×|**8**  |  |  |  |  |  |  |
|3|2|×|**9**  |  |  |  |  |  |  |

・しかし、これだと<B>一つの品物の個数が10,000個</B>とかになった時、<B>計算量がやばくなります。</B>(↓みたいな、<B>全部の品物の個数が10,000個だったらさらにヤバイ、、、</B>)

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

　　　　　　　　　　　　↓　じゃあどうするか

:::note
一個ずつに分けるのではなく、<B>「繰り返し二乗法」</B>(厳密には違う)という手法で$m_i$を分解し、計算量を減らします！！！！！
:::

## 2.2.繰り返し二乗法の「分解」

![個数制限付き.001.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/b87bcdbd-87d4-aeb0-c962-b3ba5a7a5a56.jpeg)
![個数制限付き.002.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/3d97567a-d70e-098e-ff6c-e1616003776a.jpeg)

・繰り返し二乗法に使われている<B>「分解」</B>を使うので、<B>厳密には繰り返し二乗法ではない</B>というわけですね！

### 2.2.1.この分解で何が嬉しいの？
#### 一個一個分解して計算するより、<font color="red"><B>計算量が減る！！！</B></font>

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

・例えば上の表の$i=3$の品物を考えます。

```math
\begin{align}

m_i &= 4 \\
&= 2^0+2^1+1\\
&= 1+2+1\\

\end{align}
```

に分けることができます。

・つまり品物を<B>[価値=1、重さ=2]、[価値=2、重さ=4]、[価値=1、重さ=2]</B>に分解して、各品物ごとに、入れるか入れないか(0-1ナップ)をします。

![個数制限付き.003.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/d6cd8f7f-0262-616b-3c8f-3dda65b7bb1c.jpeg)

・$m_i=10000$とかになると、さらに計算量を減らすことができます。

・全ての品物を分解したら、あとは0-1ナップサック問題と同じ、入れるか入れないかを考えていきます。

## 2.3.DPテーブルを作る

・DPテーブルの埋め方は<B>0-1ナップサック問題</B>と同じ考え方です。

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

$$\boldsymbol{dp[i][j]=i番目までの品物を使って、容量がjを超えないような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.
```

としてdp表を埋めていきます。
:::

## 2.4.実装

```python
# 入力値取得
N,W=map(int,input().split())
    
# mi(品物の個数)を分解した後の、v(価値)とw(重さ)を入れるリストを作る
L=[]
for _ in range(N):
  v,w,m=map(int,input().split())
  k=1
  while m>0:
    L.append([v*k,w*k])
    m-=k
    k=min(2*k,m)

# DP表作成(一次元)
dp=[0]*(W+1)

# 分解した品物が入ってるリストからv,wをとって回す
# 0-1ナップの一次元と同じ回し方(WとWeの違いに注意！)
for v,w in L:
  for j in range(W,w-1,-1):
    dp[j]=max(dp[j],dp[j-w]+v)
print(dp[W])
```

### 2.4.1.分解するときのコードについて
```python
for _ in range(N):
  v,w,m=map(int,input().split())
  k=1
  while m>0:
    L.append([v*k,w*k])
    m-=k
    k=min(2*k,m)
```
・分解する時の↑のコードの流れを少しだけ詳しくみていきたいと思います。

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

・上の表の<B>i=3(3番目の品物)</B>の時を例に考えます。

![個数制限付き.004.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/ebf2aad0-8fd6-bd47-ba49-626e53dff570.jpeg)
![個数制限付き.005.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/bf9fe35e-d028-8903-40df-0bf9439316f2.jpeg)
![個数制限付き.006.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/5deeb0ef-67a3-e198-1c3c-3b0dc066fcc8.jpeg)
![個数制限付き.007.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/1b8f05e9-8add-88e6-952d-fa99df04dafd.jpeg)
![個数制限付き.008.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/3f5384b8-5e03-1c7d-de74-b015eb7f03d1.jpeg)
![個数制限付き.009.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/bea046b9-be64-e73b-1180-7203aeb3e93a.jpeg)
![個数制限付き.010.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/cf5a3897-d988-33e5-9213-7f08aa5b97ef.jpeg)
![個数制限付き.011.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/c1f9a616-fb34-40ed-9fa8-bd9551be10fc.jpeg)
![個数制限付き.012.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/c87cd99b-f995-0470-08d7-ae3957d91032.jpeg)
![個数制限付き.013.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/a8914b26-a03a-e7b9-2f03-a932858b45ff.jpeg)
![個数制限付き.014.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2658998/e857aec5-e8a3-f1ce-b5f3-cc3d700cba47.jpeg)

・みたいな感じです。