Submission #7070891

---

Source Code Expand

# 入力
N, W = map(int, input().split())

weight = []
value = []

for i in range(N):
    input_array = list(map(int, input().split()))
    value.append(input_array[0])
    weight.append(input_array[1])

# dpの初期値（i + 1に入れていくので、ひとつ多く準備する）
range_num = max(N, W)
dp = [[0 for i in range(range_num + 1)] for j in range(range_num + 1)]

# 動的計画法で最大値を求める
# 選ぶ個数のループ
for i in range(N):
    # 各重さのループ
    for j in range(W + 1):
        # 重さがWを超えない時の最大値を計算
        if (j >= weight[i]):
            dp[i + 1][j] = max(dp[i][j - weight[i]] + value[i], dp[i][j])
        else:
            dp[i + 1][j] = dp[i][j]
    
# 結果出力
print(dp[N][W])

Submission Info

Judge Result