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