クルトンのプログラミング教室

Pythonの使い方やPythonを使った競技プログラミングの解法などを解説しています。

Pythonで理解する蟻本「2-3 01 ナップサック問題その2」(p.60)

Pythonで理解する蟻本（プログラミングコンテストチャレンジブック）

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「2-3 01 ナップサック問題その2」(p.60)
のコードをPythonで書き直したものとなっています。

入力

n\,W\\w_1\,…\,w_n\\v_1\,…\,v_n

入力例



4 5
2 1 3 2
3 2 4 2


解答

# 入力
n, W = map(int,input().split())
w = list(map(int,input().split()))
v = list(map(int,input().split()))

MAX_N = 100
MAX_V = 100
INF = float('inf')

dp = [[INF] * (MAX_N * MAX_V + 1) for _ in range(MAX_N + 1)]    # DPテーブル
dp[0][0] = 0

for i in range(n):
    for j in range(MAX_N * MAX_V + 1):
        if j < v[i]:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i])
    res = 0
    for i in range(MAX_N * MAX_V + 1):
        if dp[n][i] <= W:
            res = i
print(res)