====== سوال ۴ ======



می‌خواهیم قطعه چوبی به طول $L$ را از نقاط مفروض $x_1,x_2,…,x_k$ ببریم. ($x_i$ فاصله‌ی نقطه‌ی $i$ ام از لبه‌ی سمت چپ چوب است.) با فرض این که بریدن چوبی به طول $\ell$ در هر نقطه، متناسب با $\ell$ هزینه دارد، الگوریتمی سریع ارائه کنید که ترتیب نقاط برش را طوری به‌دست آورد که مجموع هزینه‌های برش کمینه گردد. (نیازی به برنامه نیست.) زمان اجرای این الگوریتم چه‌قدر است؟



  * [[سوال ۵|سوال بعد]]
  * [[سوال ۳|سوال قبل]]