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

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

Pythonで理解する蟻本「2-3 個数制限付き部分和問題」(p.62)

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

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

入力

n\\K\\a_1\,a_n\\m_1\,…\,m_n

入力例



3
17
3 5 8
3 2 2


解答

bool値を求めるDP（O(Σmi)）

MAX_N = 100
MAX_K = 100000

# 入力
n = int(input())    # 列の長さ
K = int(input())    # 作りたい数
a = list(map(int,input().split()))    # 値
m = list(map(int,input().split()))    # 個数

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

dp[0][0] = True
for i in range(n):
    for j in range(K + 1):
        k = 0
        while k <= m[i] and k * a[i] <= j:
            dp[i + 1][j] |= dp[i][j - k * a[i]]
            k += 1
if dp[n][K]:
    print("Yes")
else:
    print("No")

情報量の多いDP（O(nK)）

MAX_N = 100
MAX_K = 100000

# 入力
n = int(input())    # 列の長さ
K = int(input())    # 作りたい数
a = list(map(int,input().split()))    # 値
m = list(map(int,input().split()))    # 個数

dp = [-1] * (MAX_K + 1)    # DPテーブル

dp[0] = 0
for i in range(n):
    for j in range(K + 1):
        if dp[j] >= 0:
            dp[j] = m[i]
        elif j < a[i] or dp[j - a[i]] <= 0:
            dp[j] = -1
        else:
            dp[j] = dp[j - a[i]] - 1
if dp[K] >= 0:
    print("Yes")
else:
    print("No")