ナップザック問題が良く判らない。
1次元から2次元の問題になったのだが、遷移のイメージがしっくりこない。
EDPCの問題を改良して、DP表を作成するプログラムに変更してみた。
# EDPC-D-Knapsack_2 # DP表を表示
# 入力
N, W = map(int, input().split())
# 1始まりにするために先頭にダミーを入れる
Wei=[0]
Val=[0]
for i in range(N):
w, v = map(int, input().split())
Wei.append(w)
Val.append(v)
# dp[i][w]:品物iまで見て重さ合計wであるときの価値の総和の最大値
dp=[]
# 十分小さい値
INF = -2**60
# 動的計画法用の配列
# 非常に小さい値で初期化しておく
for i in range(N+1):
dp.append([0]*(W+1))
# 初期条件(最初は何も選ばない)
dp[0][0] = 0
max_val = 0
print('i/w')
for i in range(W+1):
print("{:3}".format(i), end=' ')
print('')
# i が小さい順に求めていく
for i in range(1, N+1):
#print("{:3}".format(i))
for w in range(W+1):
# 品物 i を使わない場合
dp[i][w] = max(dp[i][w], dp[i-1][w])
# 品物 i を使う場合
if w-Wei[i]>=0:
dp[i][w]=max(dp[i][w], # 品物を選ばない場合
dp[i-1][w-Wei[i]]+Val[i]) # 品物を選ぶ場合(価値の総和)
print("{:3}".format(dp[i][w]), end=' ')
max_val = max(max_val, dp[i][w])
print('')
print(max_val)
以下、次のデータでのDP表です。
6 15
6 5
5 6
6 4
6 6
3 5
7 2
i/w
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 0 0 0 0 0 5 5 5 5 5 5 5 5 5 5
0 0 0 0 0 6 6 6 6 6 6 11 11 11 11 11
0 0 0 0 0 6 6 6 6 6 6 11 11 11 11 11
0 0 0 0 0 6 6 6 6 6 6 12 12 12 12 12
0 0 0 5 5 6 6 6 11 11 11 12 12 12 17 17
0 0 0 5 5 6 6 6 11 11 11 12 12 12 17 17