পাইথনে একটি লাঠি কাটতে ন্যূনতম খরচ খুঁজে বের করার প্রোগ্রাম

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

সুতরাং, ইনপুট যদি n =7, cuts =[5,1,4,3] এর মত হয়, তাহলে আউটপুট হবে 16 কারণ যদি আমরা সেগুলিকে [3,5,1,4] এর মতো অর্ডার করি, তাহলে প্রথমে কাটবে 7 এর দৈর্ঘ্য থেকে 3, তাই খরচ হল 7, তারপরে আমাদের দৈর্ঘ্য 3 এবং 4 এর দুটি অংশ আছে, তারপর 5 এ কাটে, তাই খরচ 4, এখন পর্যন্ত মোট 7+4=11, তারপর লাঠি সাইজ 2 থেকে 4 এ কাট , তাই মোট খরচ 7+4+2 =13, তারপর শেষ পর্যন্ত 3 কাটে তাই খরচ হয় 3, এবং চূড়ান্ত খরচ 7+4+2+3 =16।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

cuts :=একটি তালিকা যেখানে কাটের উপাদানগুলি সাজানো হয় এবং শুরুতে 0 এবং শেষে n ঢোকান
m :=কাটের আকার
খরচ :=m x m আকারের একটি বর্গাকার ম্যাট্রিক্স তৈরি করুন এবং 0
দিয়ে পূরণ করুন
k এর জন্য 2 থেকে m - 1 রেঞ্জে, করুন
- আমি 0 থেকে m - 1 রেঞ্জের জন্য, কর
  - j :=i + k
  - যদি j>=m হয়, তাহলে
    - পরবর্তী পুনরাবৃত্তির জন্য যান
  - খরচ[i, j] =(কাট[j] - কাট[i]) + ন্যূনতম (খরচ[i, s] + খরচ[s, j] সমস্ত রেঞ্জের জন্য (i+1, j-1))
- ফেরত খরচ[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]