[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])Reference
この問題について([BOJ 12865]普通リュック(Python)), 我々は、より多くの情報をここで見つけました https://velog.io/@uoayop/BOJ-4781-평범한-배낭Pythonテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol