読者です 読者をやめる 読者になる 読者になる

ナップザンク問題

動的計画法 メモ化 メモ化再帰

dp(i, j)を以下のように定義する。


dp(i, j) := i番目の荷物を重さj以下のなるように操作した時(その荷物を入れるか否か)の最大の価値


深さ優先で、その荷物を入れる場合と入れない場合とを比べ、価値がより大きくなるものを選択していく。