DPL_1_B: 0-1 Knapsack Problem (続き)

さて逆転させてみる

重さ0とか品物0の場合は価値0
n個めまでの荷物を使って重さの総和tまで持った時の価値は

n個めの荷物を使わないとき：
(n-1)個めまでの荷物を使って重さの総和tまで持った時の価値

n個めの荷物を使うとき：
(n-1)個めまでの荷物を使って重さの総和(t - n個めの重さ)まで持った時の価値＋
n個めの価値

のうちの大きいほう
コードに直すとこう

def knapsack(
    total_weight: int, n_baggages: int, baggages: List[Baggage]
) -> int:

    T: List[List[int]] = [
        [0] * (n_baggages + 1) for _ in range(total_weight + 1)
    ]

    for n in range(1, n_baggages + 1):
        for t in range(1, total_weight + 1):
            v = T[t][n - 1]
            b = baggages[n - 1]
            if t >= b.weight:
                v_use = T[t - b.weight][n - 1] + b.value
                v = max(v, v_use)
            T[t][n] = v

    return T[total_weight][n_baggages]

AC
こういうときは1オリジンでやりたい

解説を読む
やってることはほぼ同じか
どの品物を選択したかを記録している
問題によっては必要になりそう