アルゴリズムのとびら　その4

はじめに

これまでの3回で、効率の良い手順（アルゴリズム）を考えてきました。
今回はこれまでの手順をプログラムにして、お宝と船のお話を一区切りします。

勇者ねこの冒険

重量制限のある船に、できるだけ合計の値段が高くなるようにお宝を載せる方法を考えた勇者ねこ。
これまでに考えた手順をそれぞれプログラムにしてみました。

1. 全ての組み合わせを一つずつ計算するプログラム
2. 枝刈りするプログラム（途中で重量制限を超えるとわかったら計算しない）
3. それまでの計算結果をメモして利用するプログラム

パソコンも持って、新しい冒険に出発します！

海を冒険して宝島を発見しました！

お宝の番号	重さ	値段
1のお宝	1kg	20万ポイント
2のお宝	2kg	5万ポイント
3のお宝	3kg	10万ポイント
4のお宝	8kg	40万ポイント
5のお宝	7kg	15万ポイント
6のお宝	4kg	25万ポイント
7のお宝	5kg	50万ポイント
8のお宝	6kg	30万ポイント
9のお宝	2kg	10万ポイント
10のお宝	9kg	10万ポイント
11のお宝	7kg	32万ポイント
12のお宝	kg4	18万ポイント
13のお宝	5kg	15万ポイント
14のお宝	6kg	20万ポイント
15のお宝	2kg	5万ポイント

「プログラムを使って、合計の値段が一番高くなる組み合わせを見つけよう！」

船に載せられる重さの上限（5～30）(kg)

プログラム実行結果

勇者ねこは無事にお宝を持ち帰りました。やったね！

まとめ

これまでに考えた計算の手順（アルゴリズム）をもとに、プログラムを作成することができました。
効率的なアルゴリズムを使えば、計算にかかる時間を短くできます。
今回はお宝が15個でしたが、これが100個、1000個と増えると、計算時間の差も大きく開いていきます。

「アルゴリズムのとびら　その1」から今回までに扱ったテーマ（重量制限内で最大の価値になる組み合わせを求める）は、「ナップザック問題」と呼ばれる問題です。
実はこの問題、枝刈りやメモ化で効率化はできても、お宝の数が増えるとどうしても計算に時間がかかってしまいます。
効率よく答えを求める方法を見つけられたら大発見です！　この先見つかるかもしれませんね。