Educational DP Contest D - Knapsack 1 / E - Knapsack 2【Python解答例】 - ebisukeプログラミング初心者脱出黙示録

f:id:ebisuke33:20210322211538p:plain
今回もEDPCをPythonで解いてみようと思います。
DとE問題が似ていましたので合わせて記事にしました。

参考にした記事はこちらです。勉強になります。
動的計画法超入門！ Educational DP Contest の A ～ E 問題の解説と類題集 - Qiita

EDPC D - Knapsack 1

問題文

N個の品物があります。品物には1,2,…,Nと番号が振られています。各i(1≤i≤N) について、品物iの重さはwiで、価値はviです。
太郎君は、N個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。ナップサックの容量はWであり、持ち帰る品物の重さの総和はW以下でなければなりません。
太郎君が持ち帰る品物の価値の総和の最大値を求めてください。

制約

・入力はすべて整数である。
・1≤N≤100
・1≤W≤10^5
・1≤wi≤W
・1≤vi≤10^9

解答例

n, w = map(int,input().strip().split())
wv = []
for i in range(n):
    array = list(map(int, input().strip().split()))
    wv.append(array)

dp = [[0 for j in range(100010)]for i in range(110)]  # ※1

for i in range(n):
    for sum_w in range(w+1):
        if sum_w - wv[i][0] >= 0:
            dp1 = dp[i][sum_w - wv[i][0]] + wv[i][1]
        dp2 = dp[i][sum_w]
        if sum_w - wv[i][0] >= 0 and dp1 > dp[i+1][sum_w]:
            dp[i+1][sum_w] = dp1
        if dp2 > dp[i+1][sum_w]:
            dp[i+1][sum_w] = dp2

print(dp[n][w])

解説

この問題はナップサック問題と呼ばれ、動的計画法の典型的な問題のようです。
N個の品物があり、それぞれの品物に重さと価値があります。
重さWまで荷物が入るナップサックにできるだけ価値が高くなるように品物を詰め込もうとしています。

まずは※1のように二次元配列dpを用意しました。
dp[a][b]の場合、a番までの品目から重さbを超えないように選んだ価値の最大値を格納していきます。
荷物の個数Nは100まで、重さWは10^5までと制約があるのでそれぞれの制約より10ずつ要素数を増やしました。
要素はすべて0にしたので、初期条件も満たします。（なにも選んでいないときは価値も0なので）
次に品目と重さの2重ループとなっています。
i番目の品目を選ぶ場合はdp1のように価値wv[i][1]を加算します。
sum_wからi番目の品目の重さwv[i][0]を引いた値が0より小さくなることは条件的に不適切ですので、sum_w - wv[i][0] >= 0が成り立つときだけdp1を計算しています。
dp2は品目を選ばない場合で、価値は変わりません。
dp[i+1][sum_w]にはdp1とdp2のうち大きいほうを代入しています。
この処理を繰り返してdp[n][w]まで計算し、出力すればACでした。
今回もPythonでは時間オーバーとなりましたのでPyPyで提出しました。

EDPC E - Knapsack 2

E - Knapsack 2

問題文

制約

・入力はすべて整数である。
・1≤N≤100
・1≤W≤10^9
・1≤wi≤W
・1≤vi≤10^3

解答例

n, w = map(int,input().strip().split())
wv = []
for i in range(n):
    array = list(map(int, input().strip().split()))
    wv.append(array)

dp = [[float('inf') for j in range(100010)]for i in range(110)]
dp[0][0] = 0

for i in range(n):
    for sum_v in range(100010):
        if sum_v - wv[i][1] >= 0:
            dp1 = dp[i][sum_v - wv[i][1]] + wv[i][0]
        dp2 = dp[i][sum_v]
        if sum_v - wv[i][1] >= 0 and dp1 < dp[i+1][sum_v]:
            dp[i+1][sum_v] = dp1
        if dp2 < dp[i+1][sum_v]:
            dp[i+1][sum_v] = dp2

ans = 0
for sum_v in range(100010):
    if dp[n][sum_v] <= w:
        ans = sum_v
        
print(ans)