DPL_1_B: 0-1 Knapsack Problem
ナップザック問題ってやつ
よく聞くけどよく知らなかったり
0-1っていうのは入れるか入れないかってことかな
ヒントの絵、やっぱり二次元の表だけど矢印が違う
そんなに本質的な差な気はしないけどどうかな
とにかくまずは再帰で書いてみよう
コインの問題とおおよその形は同じなんじゃないの
from typing import List, NamedTuple
class Baggage(NamedTuple):
value: int
weight: int
def knapsack(
total_weight: int, n_baggages: int, baggages: List[Baggage]
) -> int:
def rec(t: int, n: int) -> int:
if n < 0:
return 0
if t < baggages[n].weight:
return rec(t, n - 1)
else:
return max(
rec(t - baggages[n].weight, n - 1) + baggages[n].value,
rec(t, n - 1),
)
return rec(total_weight, n_baggages - 1)
def main() -> None:
N, W = [int(x) for x in input().split()]
B: List[Baggage] = []
for _ in range(N):
v, w = (int(x) for x in input().split())
B.append(Baggage(v, w))
print(knapsack(W, N, B))
main()
Case #14でTLE
lru_cache
でAC
再帰で書くと、書いてみたら意外と動いちゃうってことも多いけど
うまく動かないときにデバッグしにくい気もする
最初こうしててだいぶ悩んだ
if n < 0 or t < baggages[n].weight:
return 0