ナップザンク問題

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

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

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