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オリジンでやりたい
解説を読む
やってることはほぼ同じか
どの品物を選択したかを記録している
問題によっては必要になりそう