[Python] 01ナップサック問題 ABC032D

#[ABC032D](https://atcoder.jp/contests/abc032/tasks/abc032_d)

#01ナップサック問題
* N個の荷物があり、$i(1\le i\le N)$ 番目の荷物には価値 $v_i$ と重さ $w_i$ が割り当てられている。
* 許容重量Wのナップサックが１つある。
* 重さの和がW以下となるように荷物の集合を選びナップサックに詰め込むとき、価値の和の最大値を求めよ。ただし、同じ荷物は一度しか選ぶことができない。

次の３パターンのデータセットが与えられる。

* ①　$1\le N\le 30, 1\le W \le 10^9, 1\le v_i \le 10^9, 1\le w_i \le 10^9$
* ②　$1\le N\le 200, 1\le W \le 10^9, 1\le v_i \le 10^9, 1\le w_i \le 1000$
* ③　$1\le N\le 200, 1\le W \le 10^9, 1\le v_i \le 1000, 1\le w_i \le 10^9$

時間計算量と空間計算量の制約に対応するために、それぞれのパターンに応じた計算方法を採る必要がある。

#➀　N≦30
全列挙 $O(2^N)$ ではTLEになる。
動的計画法は、空間計算量が膨大でMLEになる。
枝刈りで行けそうだが、半分全列挙 $O(2^\frac{N}{2}\log {2^\frac{N}{2}})$ で確実に行う。
高速に探索できるように、最大値を実現できる可能性のある [重み,価値] のみを列挙する。

#➁　w≦1000
空間計算量に配慮し、動的計画法を次のように設計する。一般的なナップサック問題の解法となる。
時間計算量は $O(N^2 W_{max})$ で空間計算量は $O(NW_{max})$ となる。

$dp[i][j]$の定義：
$i$ 番目までの荷物を選んで、重みの和 $j$ 以下を満たす、価値の和の最大値

dp初期条件：

```math
dp[0..N][0..W]=0
```

dp漸化式の定義：

```math
dp[i][j]=max(dp[i-1][j], dp[i-1][j-w_i]+v_i) \hspace{15pt}(j-w_i\ge 0)
```

求める解：

```math
dp[N][W]
```

#➂　v≦1000
空間計算量に配慮し、動的計画法を次のように設計する。
時間計算量は $O(N^2 V_{max})$ で空間計算量は $O(NV_{max})$ となる。

$dp[i][j]$の定義：
$i$ 番目までの荷物を選んで、価値の和 $j$ を達成する、重みの和の最小値

dp初期条件：

```math
dp[0][0]=0,  dp[0..N][0..V_{max}]=\infty
```

dp漸化式の定義：

```math
dp[i][j]=min(dp[i-1][j], dp[i][j-v_i]+w_i) \hspace{15pt}(j-v_i\ge 0)
```

求める解：

```math
max\{\ j\ |\ dp[N][j]\le W\ \}
```

PyPy3ならACするが、Python3ではTLEとなる。

```python:サンプルコード
N,W = map(int,input().split())
vw = [list(map(int,input().split())) for _ in [0]*N]

vM,wM = 0,0
for v,w in vw:
    vM = max(vM,v)
    wM = max(wM,w)

if wM <= 1000: # ➁
    wS = sum(w for v,w in vw)
    if wS <= W:
        ans = sum(v for v,w in vw)
    else:
        dp = [[0]*(W+1) for _ in range(N+1)]
        for i,vw2 in enumerate(vw,1): # イテラブルオブジェクトとインデックスを取得
            v,w = vw2
            for j in range(W+1):
                dp[i][j] = dp[i-1][j]
                if j>=w : dp[i][j] = max(dp[i][j],dp[i-1][j-w] + v)
        ans = dp[-1][W]
    print(ans)
elif vM <= 1000: # ➂
    V = sum(v for v,w in vw)
    dp = [[W+1]*(V+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i,vw2 in enumerate(vw,1):
        v,w = vw2
        for j in range(V+1):
            dp[i][j] = dp[i-1][j]
            if j>=v : dp[i][j] = min(dp[i][j],dp[i-1][j-v]+w)
    print(max(i for i,w in enumerate(dp[-1]) if w<=W))
elif N <= 30: # ➀
  w_max = W
  V,W = zip(*vw) # Weightでソートしたい
  # N <= 30
  # 半分全列挙
  left = [(0,0)] # weight, value
  right = [(0,0)]
  for i in range(N//2):
    left += [(x+W[i],y+V[i]) for x,y in left]
  for i in range(N//2,N):
    right += [(x+W[i],y+V[i]) for x,y in right]
  left.sort() # 重さ順
  right.sort()
  def remove_worthless(li):
    temp = []
    current_value = -1
    for w,v in li:
      if w > w_max:
        break
      # wでの最大値vをリストする
      if v > current_value:
        current_value = v
        temp.append((w,v))
    return temp
  left = remove_worthless(left)
  right = remove_worthless(right)
  INF = 10**18
  right.append((INF,0))
  # double pointer
  j = 0
  x = 0
  for wL,vL in left[::-1]: # leftを逆順
    wR_max = w_max-wL
    while right[j+1][0] <= wR_max:
      j += 1
    vLR = vL + right[j][1]
    if x < vLR:
      x = vLR
  print(x)
```
次はNumpy version

```python:サンプルコード
N,w_max = map(int,input().split())
VW = [[int(x) for x in input().split()] for _ in range(N)]
V,W = zip(*VW)
 
def case_1():
  # N <= 30
  # 半分全列挙
  left = [(0,0)] # weight, value
  right = [(0,0)]
  for i in range(N//2):
    left += [(x+W[i],y+V[i]) for x,y in left]
  for i in range(N//2,N):
    right += [(x+W[i],y+V[i]) for x,y in right]
  left.sort() # 重さ順
  right.sort()
  def remove_worthless(li):
    temp = []
    current_value = -1
    for w,v in li:
      if w > w_max:
        break
      # valueを更新したものに制限
      if v > current_value:
        current_value = v
        temp.append((w,v))
    return temp
  left = remove_worthless(left)
  right = remove_worthless(right)
  INF = 10**18
  right.append((INF,0))
  # double pointer
  j = 0
  x = 0
  for wL,vL in left[::-1]:
    wR_max = w_max-wL
    while right[j+1][0] <= wR_max:
      j += 1
    vLR = vL + right[j][1]
    if x < vLR:
      x = vLR
  return x
    
def case_2():
  import numpy as np
  L = N*1000+1
  dp = np.zeros(L,dtype=np.int64) # 総重量、最大価値
  for v,w in VW:
    dp[w:] = np.maximum(dp[w:], dp[:-w] + v)
  return dp[:w_max+1].max()
 
def case_3():
  import numpy as np
  L = N*1000+1
  dp = np.zeros(L,dtype=np.int64) # 総価値、最小重量
  dp[1:] = 10**18
  for v,w in VW:
    dp[v:] = np.minimum(dp[v:], dp[:-v] + w)
  possible_value = (dp <= w_max).nonzero()[0]
  return possible_value.max()
 
if N <= 30:
  print(case_1())
elif max(W) <= 1000:
  print(case_2())
else:
  print(case_3())
```