概要
Microsoft Copilotのプロンプトを細工して、日本語プログラムを実行させようとする試みです。
ナップサック、問題をやってみた。
Ohisama prompt
架空のブログを生成することを考えます。 ブログの記事を書くことです。
構成は、
ある技術的なテーマを与えられた場合 、それに対する仮説を提案します 。
次に 仮説を裏付ける理論を示します。
計算結果を導くために、日本語プログラミングのダミーコードを書くようにしてください。
最後にその理論を検証した計算結果を示します 。
最後に 簡潔な結論を加えるという構成です。
では、「ナップサック問題」というテーマで、ブログを記事にしてみてください。
回答
ナップサック問題とは、重さと価値がそれぞれ異なる品物の集合と、重さの上限が決まったナップサックが与えられたときに、ナップサックに入れる品物の組み合わせを選ぶ問題です。この問題は、最適化や暗号解読などの分野で応用される重要な問題です。しかし、この問題はNP困難であるため、品物の数が多くなると、すべての組み合わせを試すことは現実的ではありません。そこで、近似的な解法が必要になります。
仮説
ナップサック問題の近似的な解法として、貪欲法と動的計画法の2つの方法があります。貪欲法は、品物の重さに対する価値の比率が高いものから順にナップサックに入れていく方法です。動的計画法は、ナップサックの重さの上限を小さく分割し、各分割に対して最適な品物の組み合わせを求めていく方法です。この2つの方法のうち、どちらがより良い近似解を得られるかを比較することが、このブログの目的です。
理論
貪欲法と動的計画法の理論を簡単に説明します。
貪欲法は、以下のような手順で行われます。
- 品物の集合を、重さに対する価値の比率が高いものから低いものへと並べ替える。
- 並べ替えた品物の集合から、先頭の品物を取り出す。
- 取り出した品物がナップサックに入る場合は、ナップサックに入れる。入らない場合は、捨てる。
- 品物の集合が空になるか、ナップサックがいっぱいになるまで、2と3を繰り返す。
動的計画法は、以下のような手順で行われます。
- ナップサックの重さの上限を$W$とする。$W$を$1, 2, \dots, W$という$W$個の分割に分ける。
- 各分割に対して、以下の操作を行う。
- 品物の集合を、重さが分割以下のものだけに絞る。
- 絞った品物の集合の部分集合のうち、重さの合計が分割以下で、価値の合計が最大となるものを求める。
- 求めた部分集合を、分割に対応するナップサックの解として記録する。
- $W$個の分割に対応するナップサックの解のうち、価値の合計が最大となるものを、最終的なナップサックの解とする。
ダミーコード
日本語プログラミングのダミーコードを以下に示します。このコードは、実際には動作しませんが、アルゴリズムの流れを理解するのに役立ちます。
# 貪欲法のダミーコード
品物の集合を重さに対する価値の比率で並べ替える
ナップサックの重さの上限を設定する
ナップサックの重さの合計を0に初期化する
ナップサックの価値の合計を0に初期化する
ナップサックに入れる品物の集合を空に初期化する
品物の集合が空でない間、繰り返す
品物の集合から先頭の品物を取り出す
取り出した品物の重さをナップサックの重さの合計に加える
もしナップサックの重さの合計がナップサックの重さの上限以下なら
取り出した品物の価値をナップサックの価値の合計に加える
取り出した品物をナップサックに入れる品物の集合に追加する
そうでなければ
取り出した品物の重さをナップサックの重さの合計から引く
取り出した品物を捨てる
ナップサックの価値の合計とナップサックに入れる品物の集合を出力する
# 動的計画法のダミーコード
ナップサックの重さの上限を設定する
ナップサックの重さの上限を1からナップサックの重さの上限までの分割に分ける
各分割に対応するナップサックの解を格納する配列を用意する
各分割について、繰り返す
品物の集合を重さが分割以下のものだけに絞る
絞った品物の集合の部分集合のうち、重さの合計が分割以下で、価値の合計が最大となるものを求める
求めた部分集合を配列に格納する
配列の中で、価値の合計が最大となる部分集合を出力する
計算結果
以下のような品物の集合とナップサックの重さの上限を例として考えます。
| 品物 | 重さ | 価値 |
|---|---|---|
| A | 2 | 3 |
| B | 1 | 2 |
| C | 3 | 4 |
| D | 2 | 2 |
| E | 4 | 5 |
ナップサックの重さの上限は7とします。
貪欲法で求めたナップサックの解は以下のようになります。
| 品物 | 重さ | 価値 | 重さに対する価値の比率 |
|---|---|---|---|
| B | 1 | 2 | 2 |
| A | 2 | 3 | 1.5 |
| C | 3 | 4 | 1.33 |
| E | 4 | 5 | 1.25 |
| D | 2 | 2 | 1 |
品物B, A, Cをナップサックに入れると、重さの合計が6で上限以下であり、価値の合計が9となります。品物Eを入れようとすると、重さの合計が10で上限を超えるため、入れません。品物Dは重さに対する価値の比率が最も低いため、入れません。したがって、ナップサックの解は{B, A, C}で、価値の合計は9となります。
動的計画法で求めたナップサックの解は以下のようになります。
| 分割 | 品物の集合 | 重さの合計 | 価値の合計 |
|---|---|---|---|
| 1 | {B} | 1 | 2 |
| 2 |
以上。