【Python】白俊12865平凡なリュック

リンク

白骏12865普通唇膏

DPタイプの有名な問題リュックサック問題.
問題は、私にとって、普通のリュックやDPは難しすぎて、とても普通ではないリュックです.
荷物を行とし、リュックサックの大きさを列挙した二次元メモを作成します.
一つのものを選び、リュックの大きさを一つ一つ大きくし、リュックの大きさごとに入れられるものの最大の価値をメモに書きます.
荷物の重さがリュックの大きさ(else)よりも大きいと、荷物を入れることができないので、荷物を入れる前に、品物の価値をそのまま書きます.
バッグの大きさが物を入れることができれば(if bag_size >= weight)、物を入れる価値がないと比較できます.
この品物が含まれていない場合は、以前の価値を如実に記録してください.
このアイテムを入れると、リュックサックにアイテムの重量を確保する際の価値(memo[item-1][bag_size - weight])がアイテムの価値を増加させます.
次に両者を比較して、大きな値を書きます.
一人では解けないし、他人のコードを参考にしても、理解するのに長い時間がかかりました.
最初は1人で解くときは、物の重さを中心に、荷物の重さがリュックの最大の重さ内にある場合は、それなりの価値が書かれていますが、この場合は最大の価値は見つかりません.
リュックサックの大きさを中心に、物を置いて物を取るように表現すれば、ほどけます.

正しいコード

import sys; input = sys.stdin.readline

def dp(bag):
    for item in range(1, N + 1): # 물건하나씩 꺼내서 가방에 넣어봄
        weight, value = bag.pop()
        for bag_size in range(1, K + 1): # 배낭의 크기를 최대까지 키워가며 담으며 가치를 적음
            # 물건을 담을만큼 가방이 커지면
            if bag_size >= weight:
                # 물건을 안담았을 때 가치와, 담았을 때의 가치 중 큰것을 취함
                memo[item][bag_size] = max(memo[item-1][bag_size], memo[item-1][bag_size - weight] + value)
            else: # 물건의 무게가 배낭의 크기보다 작을 경우
                memo[item][bag_size] = memo[item - 1][bag_size] # 물건 못담음 즉, 가치추가 X

N, K = map(int, input().split())
# 선택0, 무게0의 경우를 만들기 위해 각각 +1씩
memo = [([0] * (K + 1)) for _ in range(N + 1)]
bag = []
for _ in range(N):
    w, v = map(int, input().split())
    bag.append([w, v])
dp(bag)

print(memo[N][K])

知るところ👨‍💻

DPは、

を実現することが困難である.