研究帖48

そよ風さん「博士！”何でも入門書”に、ナップザック問題の解き方が書いて有りましたよ！」

ナイス博士「ほうっ、どれどれ...」

*************************************************************************

1.ナップザック内のスペースの大きさをｎとする。

2.1からｎまでの大きさのスペースを作る。

3.大きいスペースはそれより小さいスペースを内部に持つと考えられる。

4.最小の商品を、最小のスペースから最大のスペースまで順番に、可能なだけ入れる。

5.それぞれのスペースは、入っている商品の合計の価値を持っているとする。

6.次に小さい商品について、最小のスペースから最大のスペースまで順番に、もし入れ替えた方が価値が 上がるなら、入れ替える。

＊入れるスペースsxから商品xの大きさを引いた残りのスペース、s0の価値に、xの価値を足した 合計が、sxの価値より大きければ入れ替えて、それをsxの価値とする。

7.すぺての商品について小さい順に繰り返し、全部終わった時、各スペースの価値が最大となる。

*************************************************************************

そよ風さん「これをプログラムにすれば良いんです！」

ナイス博士「なるほどね。..スペースを細かく分けて、小さいスペースから計算すれば、 大きいスペースの計算の時その答えを有効利用できるわけだな。」

そよ風さん「ええっ、一度出した答えを有効利用する所は、最短経路問題と似ていますね。」

ナイス博士「うん、君が考えた”棒の切り取り問題”のアルゴリズムもそうだな。」

そよ風さん「ええ、そうですね。」

ナイス博士「さて..そうすると、スペースを定義しないといけないな。」

そよ風さん「そうですね。商品も必要ですね。」

ナイス博士「いや、商品はスペースで代用出来ると思うんだ。」

そよ風さん「そうですか。じゃ、こんな感じですか？」

*************************************************************************

【スペースの定義】インターフェースcomparebleを実装する。

＊変数

1.int型、大きさ

2.int型、価値

3.String型、名前(商品として使う時必要になる)

4.スペース型、サプスペース１

5.スペース型、サプスペース2(サブスペースは、入れ替えの計算の時使う)

メソッド

1.int型、compareTo（スペース同士の価値を比較する）

2.booleant型、replace(商品を入れ替えるかどうか計算し、入れ替えたらtrueを返す)

3.String型、toString(商品名、大きさ、価値等を返す)

*************************************************************************

そよ風さん「まず、これで１からｎまでの大きさのスペースを作ります。」

ナイス博士「うん。..で？」

そよ風さん「それぞれの商品もこのクラスから作ります。」

ナイス博士「うん、それから？」

そよ風さん「商品を入れ替える時は、その大きさを引いたスペース、サブスペース２の価値に 商品の価値を足して見て、どうするか決めます。」

ナイス博士「なるほど、じゃ、コードを書いてくれ。」

そよ風さん「はいっ..............出来ました！！」

ナイス博士「おおっ！早いな！」

test.javaのコード

InputPanel.javaのコード

Calculator.javaのコード

Space.javaのコード

簡単なクラス図 　

ナップザック問題アプレット

ナイス博士「この、インプットパネルってなんだい？」

そよ風さん「入力用のパネルをユースフルアプレット２にはめ込んで使うんです。」

ナイス博士「なるほど、ユースフルアプレット２を有効利用したんだな。」

そよ風さん「ええ、ＧＵＩを作りやすくする方法は、色々考えないとね。」

ナイス博士「うん。....じゃ、さっそく全部の商品を入力して、大きさを10にして計算しよう！」

そよ風さん「はいっ！....出来ました！まあ！5リットルのお米2個で3600円だわ！！」

ナイス博士「そうか！..これで彼女が何を買ったかわかったぞ！..しかし、5リットルの米2袋か..」

そよ風さん「ええっ...彼女は力持ちですね..」

ナイス博士「うん。只者じゃないとは思っていたが、これほどとは...」

そよ風さん「ええ....でも、簡単な答えですね。これならプログラムを作らなくてもわかった かもしれませんね。....」

ナイス博士「いいじゃないか！..他でも使えるし、作る事自体に意味があるんだ！」

そよ風さん「そうですね。彼女にも見せ付けてやれるしね！」

続く。

」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」

研究課題に戻る。

　見学者への注意事項に戻る。