ナップサック問題 - Qiita

「重さが1,3,5,6,8 という5つの品物をいくつか選んで、最も10に近づけるにはどう組み合わせればいいか」 こういう問題のことをナップサック問題といいます。 今回は1,3,6と詰めれば、丁度10になりますが、どのように組みわせてもぴったりになることはない問題もあります ナップサック問題 一次元のタイルパズルという感じで簡単そうに見えますが、完全に求めるには総当りしかない、結構厄介な問題です 品物の候補が100個ある場合、2^100通りの選び方があるのでとてもまともには計算できません そこで、枝刈りポイントを探していきましょう 多くの場合は、100個の品物があっても、せいぜい入るのは10個前後でしょう ですので、全てをチェックする必要がないことがわかります 入るパターンを効率よく探すために、以下のアルゴリズムで探索していきます まず、メモを用意して、1個目の品物の重さを書きます 2個目は