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

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

Pythonで理解する蟻本「2-3 個数制限なしナップサック問題」(p.58)

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

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

入力

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

入力例



3 7
3 4 2
4 5 3


解答

三重ループによる解法（O(nW^2)）

MAX_N = 100
MAX_W = 10000

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

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

for i in range(n):
    for j in range(W + 1):
        k = 0
        while k * w[i] <= j:
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - k * w[i]] + k * v[i])
            k += 1
print(dp[n][W])

二重ループによる解法（O(nW)）

MAX_N = 100
MAX_W = 10000

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

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

for i in range(n):
    for j in range(W + 1):
        if j < w[i]:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i + 1][j - w[i]] + v[i])
print(dp[n][W])

同じ配列を再利用した解法（O(nW)）

01ナップサック問題の場合
# 入力
n, W = map(int,input().split())
w = list(map(int,input().split()))
v = list(map(int,input().split()))

MAX_N = 100
MAX_W = 10000
dp = [[0] * (MAX_W + 1) for _ in range(MAX_N + 1)]    # dpテーブル

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

iに関するループの向きを順方向に直した動的計画法（O(nW)）

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

MAX_N = 100
MAX_W = 10000
dp = [[0] * (MAX_W + 1) for _ in range(MAX_N + 1)]    # dpテーブル

for i in range(n):
    for j in range(W + 1):
        if j < w[i]:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i])
print(dp[n][W])
01ナップサック問題の場合
MAX_N = 100
MAX_W = 10000

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

dp = [0] * (MAX_W + 1)    # DPテーブル

for i in range(n):
    for j in range(W, w[i] - 1, -1):
        dp[j] = max(dp[j], dp[j - w[i]] + v[i])
print(dp[W])
個数制限なしナップサック問題の場合
MAX_N = 100
MAX_W = 10000

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

dp = [0] * (MAX_W + 1)    # DPテーブル

for i in range(n):
    for j in range(w[i], W + 1):
        dp[j] = max(dp[j], dp[j - w[i]] + v[i])
print(dp[W])