Submission #2896985

---

Source Code Expand

def d_simple_knapsack(N, W, Baggage):
    from collections import defaultdict
    # dp[w]:ナップサックに重さがwになるように荷物を入れたときの価値の最大値
    dp = defaultdict(int)
    dp[0] = 0  # 重さ0で達成できる価値は0とする
    for w, v in Baggage:
        # dpの各要素(現時点におけるナップサック内の荷物の重さ)に対して、
        # 注目した荷物を入れても重さがWを超えなければ、
        # ナップサックに荷物を入れて価値の最大値を更新する
        tmp = defaultdict(int)  # 価値の最大値を更新できた荷物の重さの情報
        for kw, kv in dp.items():
            if kw + w <= W:
                if kw + w in dp:
                    tmp[kw + w] = max(dp[kw + w], kv + v)
                else:
                    tmp[kw + w] = kv + v
        for key, value in tmp.items():
            dp[key] = value
    ans = max(dp.values())
    return ans

N, W = [int(i) for i in input().split()]
Baggage = [[int(i) for i in input().split()] for j in range(N)]
print(d_simple_knapsack(N, W, Baggage))

Submission Info

Judge Result