[BOJ 12865]普通リュック(Python)

質問する

https://www.acmicpc.net/problem/12865

お願いします、、バッグ、、取らないで、、、
宅配便で荷物を送りましょう・・・
もしあなたがhoxy内色アルゴリズムを知らないならば、箱を読んでください~!( 🔗 リンク )

シェーディングアルゴリズム

シェーディングアルゴリズムは有名なdp問題の一つである.

とにかく、荷物をかばんに入れて、最大の価値を求めればいいのです.
この場合、特定のものがない場合、最適な値が現れる可能性があることを考慮すべきである.

問題を解く

バッグにはk kgまで入れられ、アイテムの個数はn個です.
まずdp配列を作成した.

dp = [[0 for _ in range(k+1)] for _ in range(n+1)]

# dp[i][j] = 물건 무게의 합이 j일때, 처음 i개의 아이템 중 담을 수 있는 최대 가치
# ( i = 1 ~ n / j = 1 ~ k )

# 현재 물건의 무게 w, 현재 물건의 가치 v
w = bag[i][0] 
v = bag[i][1]

現在の貨物重量がw、現在の貨物価値がvである場合、jがwより大きいと、バッグに物を入れることができません.
その時、dp[i][j]には以前のdp[i-1][j]が含まれていた.
jがw以上であれば、物を詰めることができます.
しかし、今は物を入れていないときと、物を入れているときの価値を比較した上で、もっと高い値段を加えるべきです.
[現在の価値]

dp[i][j] = dp[i-1][j-w] + v
# dp[i-1][j-w] : 현재 물건을 담기 직전, 갖고 있던 최대 가치
# v : 현재 물건의 가치

[今は物を入れない価値]

dp[i][j] = dp[i-1][j]

コード#コード#

import sys
input = sys.stdin.readline

n,k = map(int,input().rstrip().rsplit())
bag = ['dummy']

dp = [[0 for _ in range(k+1)] for _ in range(n+1)]

for _ in range(n):
    row = tuple(map(int,input().rstrip().rsplit()))
    bag.append(row)

for i in range(1,n+1):
    for j in range(1, k+1):
        # 현재 물건의 무게 w, 현재 물건의 가치 v
        w = bag[i][0] 
        v = bag[i][1]

        # 물건을 담을 수 있을 때
        if j >= w:
            # (현재 물건을 담지 않았을 때 갖는 최댓값 vs 현재 물건을 담았을 때 갖는 최댓값)
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)
        else:
            dp[i][j] = dp[i-1][j]

print(dp[n][k])