ナップサック問題!?

projecteulerのP31が未解答で詰まっている。
なんとなく、再帰で解けそうな気はしているのだけど、うまく表現できない。

一方で、この手の問題はナップサック問題に帰着できる（のか似ているのか、その辺りは？）
らしい。

コンピュータサイエンス畑を歩いているとやはり、この辺りは避けて通れなさそうな雰囲気。

とか思っていたら、先日の動的計画法で解けるという話も。

この辺り、正直よく分からん。
理解することも大事だけど、それを手元の問題にどう適用していくかが肝なんだろうな。と。
まぁ、適用できないケースもあるだろうから、その辺の見極めも含めて、なんだろうけど。