個数制限なしナップザック

はむこの解答 概要 重さw_i, 価値v_iの荷物がn種類ある。個数制限なく重さ容量Wのナップザックに積める時の価値を最大化せよ。 勉強したこと ・集めるDPのバグらせ方として、v, wの添字を-1しわすれるというのがある 方針 DP。遷移を一個外に出すことで高速化する。O(nW) 集めるDP 状態 DP[i][j] = 荷物[0, i)を使って…