ITパスポート 2013年 秋期 問12

資材4個の配分による最大利益【ITパスポート 解説】

正解の理由

解法ステップ

1. 表から各工場の「個数ごとの利益」を確認します（単位は百万円）。
   • A工場：0→0、1→2、2→5、3→7、4→8
   • B工場：0→0、1→1、2→3、3→5、4→7
   • C工場：0→0、1→3、2→4、3→6、4→8
2. 「1個増やしたときの増分（限界利益）」を求めます。限界利益とは「その工場にさらに1個配ったときに増える利益」です。
   • Aの限界利益（順に1個目→4個目）: 2、3、2、1
   • Bの限界利益: 1、2、2、2
   • Cの限界利益: 3、1、2、2
3. 資材は合計4個なので、増分が大きい順に「1個ずつ」配っていきます（毎回、次に配ったときの増分が最も大きい工場を選ぶ）。
   • 1個目：Cの1個目（増分3） → Cに1個（利益 3）
   • 2個目：Aの1個目（増分2） → Aに1個（利益 2）
   • 3個目：Aの2個目（増分3） → Aにもう1個（利益 +3 → A合計5）
   • 4個目：Aの3個目（増分2） → Aにさらに1個（利益 +2 → A合計7）
4. 結果：Aに3個で7、Cに1個で3、Bに0個で0。合計 $7+3=10$（百万円）。

選択肢別の誤答解説

• ア: 8
  8は「全部をAに渡す（Aに4個）」「全部をCに渡す（Cに4個）」など、偏った配分の利益です。どちらも合計8になりますが、より有利な分配が存在するため最大ではありません。
• イ: 9
  9は例えば「Aに2個（5）とCに2個（4）を配分」の合計 5+4=9 から来る数値です。確かに良い組合せですが、Aに3個＋Cに1個の組合せで10となり、9より小さいため不正解です。
• ウ: 10
  Aに3個（7）とCに1個（3）の合計で10となり、これが最大です（ここが正解）。表の限界利益を順に取っていくと導出できます。
• エ: 11
  11は表の数値を誤って合算した結果（例：Aに4個の8とCに1個の3を合算するなど）で出やすい誤りです。資材は合計4個なので、合計個数が4を超える配分は許されません。

よくある誤解

• 「平均利益が高い工場に全て配ればよい」→ 間違い。重要なのは「1個追加したときの増え方（限界利益）」です。最初の1個で大きな利益が出る工場にまず配るのが有利な場合があります。
• 「限界利益は順序に関係ない」→ 間違い。各工場は1個目、2個目…と段階があり、次の限界利益は前の配分状況に依存します。だから配る順序（常に現在一番増えるところを選ぶ）が大切です。
• 「小数に分ければもっと良くなるはず」→ 資材は個数で配る整数問題です。分割できない前提なら離散的な配分で考えます。

補足コラム

• 限界利益（marginal profit）という考え方：これは「あと1個配ったときに利益がどれだけ増えるか」を示す値です。日常の例で言えば、セール品を1個多く仕入れたときにその分だけ会社の利益がどれだけ増えるか、という感覚に近いです。
• 今回のように「資源が少数個で分配する」問題は、限界利益を順に比較して配る（貪欲法＝グリーディ法）で解けることが多いです。これは手順がシンプルで試験でも使いやすいテクニックです。
• すべての類似問題で貪欲法が常に最適になるわけではありません。問題の性質（限界利益が単調かどうかなど）によっては全パターン列挙や動的計画法が必要になる場合もあります。今回のような小規模の配分問題では貪欲に有効です。

FAQ