می‌خواهیم $n$ قطعه آهن $f_1$٬ $f_۲$ تا $f_n$ به ترتیب با طول‌های $l_1$٬ $l_۲$ تا $l_n$ را به همین ترتیب (از چپ به راست) به هم جوش دهیم تا یک قطعه آهن بزرگ از آن‌ها ایجاد شود. برای این کار این قطعات را به همین ترتیب پشت سرهم در یک ردیف می‌چینیم و هر بار دو تا از قطعه‌های کنار هم را برداشته٬ به هم جوش می‌دهیم و در جای قبلی‌شان قرار می‌دهیم (با این کار یک عدد از تعداد قطعه‌ آهن‌ها کم می‌شود). این کار را اگر $n-۱$ بار تکرار کنیم٬ کار به پایان رسیده است.

اما می‌دانیم که هزینه‌ی جوش دادن دو قطعه آهن کنار هم به طول‌های $a$ و $b$ برابر $a+b$ است. می‌خواهیم قطعه‌ آهن‌ها را به ترتیبی به هم جوش دهیم تا مجموع کل هزینه‌ی این کار کمینه شود.

برای این کار یک زیر مسئله‌ی $P_{ij}$ تعریف می‌کنیم که آن جوش دادن $f_i$٬ $f_{i+۱}$٬ تا $f_j$ ($i \lt j$) به هم با همین ترتیب است. هزینه‌ی کمینه‌ی این کار را $C_{ij}$ می‌نامیم.

الف. یک فرمول بازگشتی برای $C_{ij}$ و بر حسب $C_{rk}$ بنویسید به طوری که $r \lt k$ و ${k-r}\lt {j-i}$. بدیهی است که ۰ =$C_{ii}$.

ب. نشان دهید که $C_{1n}$ برای مسئله‌ی اصلی چگونه محاسبه می‌شود.

ج. برای ۵ =$n$ و ورودی ۶ =$l_۱$٬ ۲ =$l_۲$٬ ۴ =$l_۳$٬ ۳ =$l_۴$٬ ۵ =$l_۵$٬ بند «ب» را دنبال کنید و مقدار هزینه‌ی کل و ترتیب جوش دادن را به دست آورید.

• سوال بعد
• سوال قبل