سؤال ۵

۵ گونی شکر به وزن‌های ۲، ۳، ۴ و ۶ و یک گونی خالی داده‌ شده‌اند. می‌خواهیم همه‌ی شکرها را در یک گونی بریزیم. هر بار می‌توانیم یک عمل « ادغام » انجام دهیم. هر ادغام یعنی انتخاب دو عدد از گونی‌های شکر، مثلاً با وزن‌های $α$ و $b$، و یک گونی خالی، و ریختن کامل شکرهای دو گونی در گونی خالی. فرض کنید که هزینه‌ی انجام این ادغام برابر $α + b$ باشد. کم‌ترین هزینه‌های کل انجام این کار چه قدر است؟

  1. ۱۹
  2. ۴۳
  3. ۴۶
  4. ۵۱
  5. ۶۰

پاسخ

گزینه (۲) درست است.

اگر سه گونی به اوزان a،b و c چنان باشند که $a \leq b \leq c$‎ ٬ آن‌گاه با توجه به ادغام‌های گوناگون به یکی از هزینه‌های $a+2b+2c$ ، $2a+b+2c$ و یا $2a+2b+c$ خواهیم رسید که در بین آن هزینه‌ها $2a+2b+c$ کم‌ترین مقدار ممکن را دارد. بنابراین بهتر آن است که در ابتدا گونی‌های سبک‌تر را باهم ادغام کرده و حاصل را با بعدی و به همین ترتیب تا آخر پیش رویم:

\[ \left. \begin{array}{l l l l} 2+3=5\\ 4+4=8\\ 5+6=11\\ 8+11=19 \end{array} \right\}. \longrightarrow sum=43 \]