ARC 073 D - Simple Knapsack ( DP )

D: Simple Knapsack - AtCoder Regular Contest 073 | AtCoder

題意：
有 N 個物品要做 01 背包問題。背包容量 W，要求價值最大。注意有個特殊限制：所有物品的容量和第一個物品的容量的差不超過 3。

制約：
1≦N≦100
1≦W≦1e9
1≦wi≦1e9
すべての i=2,3,…,N について、w1≦wi≦w1+3
1≦vi≦1e7
W,wi,vi はすべて整数である

解法：
dp[ i ][ j ][ k ]: 已考慮前 i 個物品，已取 j 個物品，取的每一個物品容量 - 第一個物品的容量的總和為 k，此時的最大價值。
只要知道 j 和 k，就知道背包剩餘的容量是 W - ( j * w[ 0 ] + k )。

時間 / 空間複雜度：
O( N^2 * K ) / O( N * K )

from copy import deepcopy
 
N, W = map( int, input().split() )
w, v = [], []
for i in range( N ):
  _w, _v = map( int, input().split() )
  w.append( _w )
  v.append( _v )
 
dp = [ 0 for i in range( N * 3 + 1 ) ]
dp = [ deepcopy( dp ) for i in range( N + 1 ) ]
for i in range( N ):
  for j in range( i, -1, -1 ):
    for k in range( j * 3, -1, -1 ):
      if j * w[ 0 ] + k + w[ i ] <= W:
        dp[ j + 1 ][ k + w[ i ] - w[ 0 ] ] = max( dp[ j + 1 ][ k + w[ i ] - w[ 0 ] ], dp[ j ][ k ] + v[ i ] )
 
print( max( map( max, dp ) ) )