مسابقه شماره ۲۴۶
سوال
۵ گونی شکر به وزن‌های ۲ ٫ ۳ ٫ ۴ ٫ ۴ و ۶ و یک گونی خالی داده شده‌اند. می‌خواهیم همه شکرها را در یک گونی بریزیم. هر بار می‌توانیم یک عمل ادغام انجام دهیم. هر ادغام یعنی انتخاب دو عدد از گونی‌های شکر ٫ مثلا با وزن‌های a و b و یک گونی خالی و ریختن کامل شکرهای دوگونی در گونی خالی ٫ فرض کنید که هزینه انجام این ادغام برابر a + b باشد ٫ کمترین هزینه کل انجام این کار چقدر است ؟
پاسخ
اگر سه گونی به اوزان a ٫ b و c چنان باشند که a ≤ b ≤ c ٫ آنگاه با توجه به ادغام‌های گوناگون به یکی از هزینه‌های a+2b+2c ٫ 2a+b+2c و یا 2a+2b+c خواهیم رسید که در بین آن هزینه‌ها 2a+2b+c کمترین مقدار ممکن را دارد.
بنابراین بهتر آن است که در ابتدا گونی‌های سبک‌تر را با هم ادغام کرده و حاصل را با بعدی و به همین ترتیب تا آخر پیش رویم :
2 + 3 = 5 (هزینه ۵)
4 + 4 = 8 (هزینه ۸)
5 + 6 = 11 (هزینه ۱۱)
8 + 11 = 19 (هزینه ۱۹)
که مجموع هزینه‌ها برابر است با ۴۳