পাইথনে স্টিক কাট করার ন্যূনতম খরচ বের করার প্রোগ্রাম

মনে করুন একটি মান n এবং cuts নামক একটি অ্যারে আছে। একটি কাঠামো স্টিক আছে যার দৈর্ঘ্য n ইউনিট। স্টিক ০ থেকে n পর্যন্ত লেবেল করা। cuts[i] হলো একটি পজিশন যেখানে কাটা যায়। আমরা কাটা অর্ডার বদলাতে পারি। এক কাটের খরচ হলো কাটা হচ্ছে সেই স্টিকের দৈর্ঘ্য, এবং মোট খরচ সব কাটের খরচের যোগফল। ন্যূনতম মোট খরচ বের করতে হবে।

যেমন, ইনপুট n = 7, cuts = [5,1,4,3] হলে, আউটপুট হবে ১৬ কারণ অর্ডার [3,5,1,4] করলে: প্রথমে ৩-এ কাটা (স্টিক দৈর্ঘ্য ৭) খরচ ৭, দুই অংশ ৩ ও ৪। তারপর ৫-এ কাটা (দৈর্ঘ্য ৪) খরচ ৪, মোট ১১। তারপর ৪-এ কাটা (দৈর্ঘ্য ২) খরচ ২, মোট ১৩। শেষে ১-এ কাটা (দৈর্ঘ্য ৩) খরচ ৩, মোট ১৬।

সমাধান পদ্ধতি

এই সমস্যাটি সমাধান করতে নিচের ধাপগুলো অনুসরণ করুন:

cuts := সর্টেড cuts, শুরুতে ০ এবং শেষে n ইনসার্ট করুন
m := cuts-এর সাইজ
cost := ০ দিয়ে m x m স্কোয়ার ম্যাট্রিক্স
k = 2 থেকে m-1 পর্যন্ত
- i = 0 থেকে m-1 পর্যন্ত
  - j := i + k
  - যদি j >= m হয়, তবে নেক্সট ইটারেশনে যান
  - cost[i][j] = (cuts[j] - cuts[i]) + min(cost[i][s] + cost[s][j] for s in range(i+1, j))
cost[0][m-1] রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বোঝার জন্য:

def solve(n, cuts):    cuts = [0] + sorted(cuts) + [n]    m = len(cuts)    cost = [[0]*m for _ in range(m)]    for k in range(2, m):       for i in range(m):          j = i + k          if j >= m:             continue          cost[i][j] = (cuts[j]-cuts[i]) + min(cost[i][s] + cost[s][j] for s in range(i+1, j))    return cost[0][m-1] n = 7 cuts = [5,1,4,3] print(solve(n, cuts))

ইনপুট

7, [5,1,4,3]