# 練習問題

## 知識の確認

### 毎回最大の硬貨を選べば最適になるか

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

<!-- numbered-subquestions -->

1. 「残りの金額を超えない最大の額面を毎回選ぶ」方法を実行し、選ぶ硬貨を書いてください。
2. より少ない枚数で済む方法はありますか。あれば一つ挙げ、なければ理由を説明してください。
3. このことから、この貪欲法の戦略が任意の硬貨の額面で正しいといえますか。

??? success "解答例"

    1. 貪欲法では `10 + 1 + 1 + 1 + 1` の順に選び、計 5 枚になります。

    2. より少ない枚数で済む方法があります。`7 + 7` なら 2 枚だけです。

    3. いえません。この反例は、任意の額面に対して、その時点で選べる最大の額面を選んでも、最少枚数になるとは限らないことを示します。
        目先の最大の選択によって、その後のよりよい組み合わせを使えなくなる可能性があります。

### ナップサックに先に入れる品物

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

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

<!-- numbered-subquestions -->

1. 各品物の 1 キログラム当たりの価値はいくつですか。どちらを先に入れますか。
2. 分割可能ナップサック問題の貪欲法の戦略で満杯にすると、最終的な価値はいくつですか。
3. 品物を分割でき、重さの合計に制限がある場合、選択時に比べるべきなのは総価値と 1 キログラム当たりの価値のどちらですか。理由も説明してください。

??? success "解答例"

    1. 1 キログラム当たりの価値は、A が `20 ÷ 4 = 5`、B が `18 ÷ 3 = 6` です。
        したがって、単位当たりの価値が高い B を先に入れます。

    2. まず B を全部入れ、3 キログラムを使って価値 18 を得ます。残りの容量は 1 キログラムなので、
        A を 1 キログラム入れて価値 5 を得ます。最終的な価値は `18 + 5 = 23` です。

    3. 制限されるのは重さの合計であり、品物は分割できるため、単位重量当たりの価値を比較すべきです。
        A は総価値こそ高いものの、1 キログラム当たりの価値は B より低く、先に A を全部入れると価値 20 しか得られません。

### 二つのポインタを次にどう動かすか

仕切り板の高さが `[1, 8, 6, 2, 5]` で、両端から始める二つのポインタで最大容量を探します。
容量は「二枚のうち短い仕切り板の高さ × 二枚の仕切り板のインデックスの差」です。

<!-- numbered-subquestions -->

1. 初期状態で左ポインタはインデックス 0、右ポインタはインデックス 4 にあります。現在の容量はいくつですか。次にどちらのポインタを動かしますか。
2. 問い 1 の選択に従って一回動かすと、各ポインタはどのインデックスにありますか。そのときの容量はいくつで、次はどちらを動かしますか。
3. 現在の一組の仕切り板では、短い板に対応するポインタも、長い板に対応するポインタも動かせます。より大きな容量を得られる可能性が残るのはどちらですか。理由も説明してください。

??? success "解答例"

    1. 現在の容量は `min(1, 5) × (4 - 0) = 4` です。左の板が短いため、左ポインタを動かします。

    2. 左ポインタを動かすと、二つのポインタはインデックス 1 と 4 にあります。現在の容量は
        `min(8, 5) × (4 - 1) = 15` です。右の板が短いため、次は右ポインタを動かします。

    3. 短い板に対応するポインタを動かした場合にだけ、より大きな容量を得られる可能性が残ります。長い板を動かすと、板の間の距離は必ず短くなり、容器の高さは、動かしていない短い板に引き続き制限されるため、
        変わらないか低くなるだけです。したがって、容量は移動前を超えられません。短い板を動かして初めて、より高い板に出会える可能性があります。

## プログラミング演習

### 分割可能ナップサック問題

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

??? tip "解くためのヒント"

    1. まず各品物の単位重量当たりの価値 val[i] / wgt[i] を計算し、除算の結果は小数部分も保持します
    2. 単位当たりの価値が高い品物から先に入れます
    3. 残りの容量が現在の品物の重さより小さければ、ちょうど満杯になる分だけを入れて終了します