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