次のような質量と価格を持つ商品が１個ずつあります。

　　　　　24kg = 10800円　　　　19kg = 9500円　　　　13kg = 9100円

　　　　　9kg = 7200円　　　　5kg = 4500円　　　　4kg = 4000円　　　　2kg = 5000円

　　（１）　何個か選んで総量をちょうど50kgにする方法は何通りあるでしょうか？
　　（２）　総量50kg以下で総価格を最高にするための選び方を示してください。


十進BASIC で次のようなプログラムを組んで実行すると、 答えが出ます。

（１）

　　　　　　次の３通りです。

　　　　　　　　　19kg　+　13kg　+　9kg　+　5kg　+　4kg　=　50kg
　　　　　　　　　24kg　+　13kg　+　9kg　+　4kg　　　　 　　=　50kg
　　　　　　　　　24kg　+　19kg　+　5kg　+　2kg　　　　 　　=　50kg


（２）

　　　　　　　　　19kg　+　13kg　+　9kg　+　5kg　+　2kg　=　48Kg

　　　　　　　　　9500円　+　9100円　+　7200円　+　4500円　+　5000円　=　35300円


（３） ナップザック問題

　 こういった最適化問題を、 以上の様な「 しらみつぶし法 」でなく、 動的計画法を用いて解いたとき、 それは「 ナップザック問題 」と言われます。 動的計画法とは、 途中の計算結果を再利用して効率化を計る最適化問題の手法の一つです。 では動的計画法を用いてさっきの問題（２）を解いてみましょう。




　 このプログラムのアルゴリズムを理解しやすくするために、 次のようなプログラムを作ってみました。