15.6   演習¶

15.6.1   確認問題¶

1.   毎回最大の硬貨を選べば必ず最善か¶

硬貨の額面は [1, 7, 10]、目標金額は 14 です。

1. 「残りの金額を超えない最大の額面を毎回選ぶ」という方法を使い、選ぶ硬貨を書いてください。
2. より少ない硬貨を使う方法はありますか？ある場合は 1 つ書き、ない場合は理由を説明してください。
3. この結果から、この貪欲戦略がどのような硬貨の額面でも正しいといえますか？

2.   ナップサックに先に入れる品物¶

容量 4 キログラムのナップサックに、次の品物を入れます。品物の一部だけを入れることもでき、 得られる価値は入れた重さに比例します。

• 品物 A：重さ 4 キログラム、価値 20。
• 品物 B：重さ 3 キログラム、価値 18。

1. 2 つの品物の 1 キログラム当たりの価値は、それぞれいくつですか？どちらを先に入れるべきですか？
2. 分数ナップサックの貪欲戦略に従ってナップサックを満たすと、最終的な価値はいくつですか？
3. 品物を分割でき、ナップサックに総重量の制限がある場合、品物を選ぶときに比較すべきなのは、総価値と 1 キログラム当たりの価値のどちらですか？その理由も説明してください。

3.   2 つのポインタを次にどう動かすか¶

仕切り板の高さが [1, 8, 6, 2, 5] であるとき、先頭と末尾に置いた 2 つのポインタを使って最大容量を求めます。 容量は「2 枚の仕切り板のうち低いほうの高さ × 2 枚の仕切り板のインデックスの差」です。

1. 最初は左のポインタがインデックス 0、右のポインタがインデックス 4 にあります。現在の容量はいくつですか？次にどちらのポインタを動かしますか？
2. 問い 1 で選んだポインタを 1 回動かした後、2 つのポインタはそれぞれどのインデックスにありますか？このときの容量はいくつですか？次はどちらのポインタを動かしますか？
3. 現在の 2 枚の仕切り板について、低い仕切り板のポインタを動かすことも、高い仕切り板のポインタを動かすこともできます。より大きな容量を得られる可能性が残るのはどちらですか？その理由も説明してください。

15.6.2   プログラミング演習¶

1.   分数ナップサック¶

同じ長さの配列 wgt と val が与えられ、wgt[i] > 0、val[i] >= 0、ナップサックの容量は cap >= 0 です。 各種類の品物は 1 個ずつしかありませんが、その一部だけを入れることもできます。 得られる価値は、入れた重さがその品物の総重量に占める割合に応じて決まります。貪欲法を使い、 ナップサックで得られる最大の総価値を実数で返してください。

ご意見、ご質問、ご提案があればぜひコメントしてください