۵ گونی شکر به وزنهای ۲، ۳، ۴ و ۶ و یک گونی خالی داده شدهاند. میخواهیم همهی شکرها را در یک گونی بریزیم. هر بار میتوانیم یک عمل « ادغام » انجام دهیم. هر ادغام یعنی انتخاب دو عدد از گونیهای شکر، مثلاً با وزنهای α و b، و یک گونی خالی، و ریختن کامل شکرهای دو گونی در گونی خالی. فرض کنید که هزینهی انجام این ادغام برابر α + b باشد. کمترین هزینههای کل انجام این کار چه قدر است؟
پاسخ
گزینه (۲) درست است.
اگر سه گونی به اوزان 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