BOJ 12865普通リュック

5822 ワード
2021.02.12 テキストリンク
https://www.acmicpc.net/problem/12865
2秒、128 MBメモリ
input :
  • N K(1 ≤ N ≤ 100)(1 ≤ K ≤ 100,000)
  • W V(1 ≤ W ≤ 100,000)(0 ≤ V ≤ 1,000)
    • output :
  • リュックサックを入れることができるものの価値の和の最高値出力
    • 最初はグリディでできるかどうか考えていましたが、すべてのものを入れるかどうかを判断する必要があります.
    だからやるのは?
    私たちは(重量、価値)を縛って入力を受け入れます.そして、すべての場合、これを持っていくともっと価値があるかどうかを確認する必要があります.
    最初に入力したものを確認する前に.0回目の時は何もなかったので.
    tempを0にリセットします.
    tempはcurrent idx以前のprev idxの各重量から最大の価値を含む.
    Current idxの重量、価値をwei、valと呼ぶ場合.
    今の胃を詰めるには、リュックサックの重さ(w)がもっと大きい.
    1.現在のwei>w:
    この場合は入れられない.では、その品物を入れる前の最低価格temp[w]をans[w]に入れます.
    2. else:
    今は重さが足りますが、入れられるなら、二つの状況を比較しなければなりません.
  • val+temp[w-wei]:現在の物品の価値+残存重量の価値
  • temp[w]:以前のものに入れたときの最大のケース.
    この2種類を比較してもっと高い値段をあげます.
    • import sys

n, k = map(int, sys.stdin.readline().split())
data = []
for i in range(n):
    w, v = map(int, sys.stdin.readline().split())
    data.append((w, v))

# 바로 이전 값을 저장해놓는 DP 용
temp = [0] * (k + 1)
ans = [0] * (k + 1)

for wei, val in data:
    # 기준이 되는 w (배낭 무게) 임.
    for w in range(k + 1):
        if wei > w:
            ans[w] = temp[w]
        else:
            ans[w] = max(val + temp[w - wei], temp[w])

    for idx, item in enumerate(ans):
        temp[idx] = item

print(ans[-1])
    アルゴリズム/プログラマー/二分探索/level 4/敷石(Python使用)
    Spark概念の理解