u++の備忘録

「典型的な DP (動的計画法) のパターンを整理 Part 1 ~ ナップサック DP 編 ~ 」をPythonで解く

2月下旬に「典型的な DP (動的計画法) のパターンを整理 Part 1 ~ ナップサック DP 編 ~ 」の前半7問をPythonで解きました。ABCのD問題で時折出題されるDPの感覚をザックリと掴むことができました。

qiita.com

f:id:upura:20190325155517p:plain

1 ナップサック DP とは

問題 1: 最大和問題

n = int(input())
a = list(map(int, input().split()))

# input
# ==
# 3
# 7 -6 9
# ==

# dp[0] = 0
dp = [0]

# DP
for i in range(n):
    dp_i_1 = max(dp[i], dp[i] + a[i])
    dp.append(dp_i_1)

# print(dp)
# ==
# [0, 7, 7, 16]
# ==

print(dp[-1])

2 ナップサック問題

問題 2: ナップサック問題

N, W = list(map(int, input().split()))
weight = []
value = []

for i in range(N):
    w_tmp, v_tmp = list(map(int, input().split()))
    weight.append(w_tmp)
    value.append(v_tmp)

# initialize
dp = [0 for _ in range(W + 1)]

# DP
for i in range(N):
    dp_tmp = []
    for w in range(W + 1):
        if (w >= weight[i]):
            dp_next = max(dp[w-weight[i]] + value[i], dp[w])
        else:
            dp_next = dp[w]
        dp_tmp.append(dp_next)
    dp = dp_tmp

print(dp[-1])

3 部分和問題とその応用たち

問題 3: 部分和問題

N = int(input())
a = list(map(int, input().split()))
A = int(input())

# initialize
dp = [True if i==0 else False for i in range(A + 1)]

# DP
for i in range(N):
    dp_tmp = []
    for j in range(A + 1):
        if (j >= a[i]):
            dp_next = (dp[j-a[i]] or dp[j])
        else:
            dp_next = dp[j]
        dp_tmp.append(dp_next)
    dp = dp_tmp

print(dp[-1])

問題 4: 部分和数え上げ問題

N = int(input())
a = list(map(int, input().split()))
A = int(input())

# initialize
dp = [1 if i==0 else 0 for i in range(A + 1)]

# DP
for i in range(N):
    dp_tmp = []
    for j in range(A + 1):
        if (j >= a[i]):
            dp_next = (dp[j-a[i]] + dp[j])
        else:
            dp_next = dp[j]
        dp_tmp.append(dp_next)
    dp = dp_tmp

print(dp[-1])

問題 5: 最小個数部分和問題

N = int(input())
a = list(map(int, input().split()))
A = int(input())

# initialize
INF = 9999999999
dp = [0 if i==0 else INF for i in range(A + 1)]

# DP
for i in range(N):
    dp_tmp = []
    for j in range(A + 1):
        if (j >= a[i]):
            dp_next = min(dp[j-a[i]] + 1, dp[j])
        else:
            dp_next = dp[j]
        dp_tmp.append(dp_next)
    dp = dp_tmp

if dp[-1] != INF:
    print(dp[-1])
else:
    print(-1)

問題 6: K個以内部分和問題

N, K = list(map(int, input().split()))
a = list(map(int, input().split()))
A = int(input())

# initialize
INF = 9999999999
dp = [0 if i==0 else INF for i in range(A + 1)]

# DP
for i in range(N):
    dp_tmp = []
    for j in range(A + 1):
        if (j >= a[i]):
            dp_next = min(dp[j-a[i]] + 1, dp[j])
        else:
            dp_next = dp[j]
        dp_tmp.append(dp_next)
    dp = dp_tmp

if dp[-1] <= K:
    print("YES")
else:
    print("NO")

問題 7: 個数制限付き部分和問題

N = int(input())
a = list(map(int, input().split()))
m = list(map(int, input().split()))
K = int(input())

# initialize
dp = [0 if i==0 else -1 for i in range(K + 1)]

# DP
for i in range(N):
    dp_tmp = []
    for j in range(K + 1):
        if (dp[j] >= 0):
            dp_next = m[i]
        elif ((j < a[i]) or (dp_tmp[j-a[i]] <= 0)):
            dp_next = -1
        else:
            dp_next = dp_tmp[j-a[i]] - 1
        dp_tmp.append(dp_next)
    dp = dp_tmp

if dp[-1] >= 0:
    print("YES")
else:
    print("NO")