برش میله
میله‌ای به طول n را طوری ببُر که فروش تکه‌ها بیشترین درآمد را بدهد؛ جواب هر طول از جواب طول‌های کوتاه‌تر ساخته می‌شود.
میله‌ای به طول n داریم و prices[i − 1] قیمت تکه‌ای به طول i است. میله را چطور ببُریم (یا نبُریم) تا جمع قیمت تکه‌ها بیشترین شود؟ امتحان همه‌ی برش‌ها 2ⁿ⁻¹ حالت دارد.
- زمان:
O(n²) - حافظه:
O(n) - CLRS، بخش ۱۴.۱
قیمت تکه‌های ۱ تا ۸؛ برای طول ۸ بهترین درآمد ۲۲ است (تکه‌های ۲ و ۶).
def rod_cutting(prices):n = len(prices)r = [0] * (n + 1)cut = [0] * (n + 1)for j in range(1, n + 1):best = -1for i in range(1, j + 1):value = prices[i - 1] + r[j - i]if value > best:best = valuecut[j] = ir[j] = bestreturn r[n], cut
شروع اجرا
متغیرهای محلی
نارنجی = در همین گام عوض شد
prices list
Call stack
- rod_cutting()خط 1
رشد تعداد عملیات با اندازه‌ی ورودی
میانگین ۱۲ گراف تصادفی برای هر n (با seed ثابت). نشانگر توخالی = ورودی فعلی.
- try_cut
- ورودی فعلی (n=8)
نمایش به شکل جدول
| n | try_cut |
|---|---|
| 4 | 10 |
| 6 | 21 |
| 8 | 36 |
| 10 | 55 |
| 12 | 78 |
توضیح
مسئله
میله‌ای به طول n داریم و prices[i − 1] قیمت تکه‌ای به طول i است. میله را چطور ببُریم (یا نبُریم) تا جمع قیمت تکه‌ها بیشترین شود؟ امتحان همه‌ی برش‌ها 2ⁿ⁻¹ حالت دارد.
ایده‌ی برنامه‌ریزی پویا
در هر برش بهینه، اولین تکه طولی مثل i دارد و بقیه‌ی میله (طول j − i) هم باید بهینه بریده شده باشد. پس:
r[j] = max over i of (prices[i − 1] + r[j − i])
اگر r را از طول ۱ به بالا پر کنیم، هر بار جواب طول‌های کوتاه‌تر را آماده داریم. cut[j] طول اولین تکه را نگه می‌دارد تا خود برش‌ها را هم بشود بازسازی کرد.
هزینه
دو حلقه‌ی تودرتو: O(n²) به‌جای 2ⁿ.
در trace به چه چیزی نگاه کنی
- میله‌ها همان جدول
rهستند که از چپ به راست پر می‌شود؛ فلشjطولی است که حل می‌شود. - با سطح جزئیات «هر دور حلقه» فقط پر شدن خانه‌های
rرا ببین.