Educational DP Contest: D - Knapsack 1

https://gyazo.com/170fa4d86248319d6c44701d9bcaef32

dp[start][remain]: 選択肢がstart番目以降の品物、残りの容量がremainの状態で、とり得る価値の最大値

start番目の品物を取るか取らないかで大きい方を選ぶ

code:py

N, W = map(int, input().split())

dp = [0 * (W+1) for _ in range(N+1)]

# dpN = 0 * (W+1)

for start in range(N-1, -1, -1):

w, v = wvstart

for remain in range(W+1):

if remain < w:

else:

print(dp0W)

dp[end][remain]: 選択肢がend番目までの品物、残りの容量がremainの状態で、とり得る価値の最大値

dp[remain]: 残りの容量がremainの状態の、とり得る価値の最大値

品物に関しては逐次的にしか調べないので、品物別に値をメモする必要がない？

code:py

N, W = map(int, input().split())

dp = 0 * (W + 1)

for w, v in goods:

for remain in range(W, w - 1, -1):

print(dp-1)