পাইথনে রড কাটা এবং একই দৈর্ঘ্যের রড বিক্রি করার পরে সর্বাধিক লাভের সন্ধান করার প্রোগ্রাম

ধরুন আমাদের কাছে রড দৈর্ঘ্যের একটি তালিকা আছে যাকে রডলেন বলা হয়। আমাদের কাছে লাভ এবং খরচ নামে আরও দুটি পূর্ণসংখ্যা রয়েছে, যা দৈর্ঘ্য প্রতি লাভ এবং কাট প্রতি খরচ প্রতিনিধিত্ব করে। আমরা একটি রডের প্রতি ইউনিট দৈর্ঘ্য লাভ করতে পারি কিন্তু আমরা শুধুমাত্র একই দৈর্ঘ্যের রড বিক্রি করতে পারি। আমরা একটি রডকে দুটি টুকরোতেও কাটতে পারি যাতে তাদের দৈর্ঘ্য পূর্ণসংখ্যা হয়, তবে প্রতিটি কাটার জন্য আমাদের খরচের পরিমাণ দিতে হবে। আমরা যতবার চাই একটি রড কাটতে পারি। আমাদের সর্বোচ্চ মুনাফা খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুটটি rodLen =[7, 10] লাভ =6 খরচ =4 এর মত হয়, তাহলে আউটপুট হবে 82, যেহেতু আমরা 7 দৈর্ঘ্যের রডটিকে 5 এবং 2 দৈর্ঘ্য সহ দুটি রডে কাটতে পারি। 10 দৈর্ঘ্যের রডটিকে দুটি রডে কাটুন, উভয়ের দৈর্ঘ্য 5। তারপর 5 দৈর্ঘ্যের 3টি রড বিক্রি করুন মোট লাভের জন্য (5 + 5 + 5) * 6 - (2*4) =82।

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

• n :=রডলেনের আকার
• যদি n 0 এর মত হয়, তাহলে
  • রিটার্ন 0
• l_max :=রডলেনের সর্বোচ্চ
• p_max :=0
• রেঞ্জ 1 থেকে l_max এর মধ্যে কাটানোর জন্য, করুন
  • p_cut :=0
  • রডলেনের প্রতিটি রড_লেনের জন্য, করুন
    • যদি rod_len <কেটে যায়, তারপর
      • পরবর্তী পুনরাবৃত্তির জন্য যান
    • c_count :=rod_len / cuts
    • total_len :=c_count * কাট
    • যদি rod_len হয় total_len এর সমান, তাহলে
      • c_count :=c_count - 1
    • curr_profit :=total_len * লাভ - খরচ * c_count
    • যদি curr_profit <0, তারপর
      • পরবর্তী পুনরাবৃত্তির জন্য যান
    • p_cut :=p_cut + curr_profit
  • p_max :=সর্বোচ্চ p_max এবং p_cut
• রিটার্ন p_max

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

def solve(rodLen, profit, cost):
   n = len(rodLen)
   if n == 0:
      return 0
   l_max = max(rodLen)
   p_max = 0

   for cuts in range(1, l_max + 1):
      p_cut = 0
      for rod_len in rodLen:
         if rod_len < cuts:
            continue
         c_count = rod_len // cuts
         total_len = c_count * cuts
         if rod_len == total_len:
            c_count -= 1
         curr_profit = total_len * profit - cost * c_count
         if curr_profit < 0:
            continue
         p_cut += curr_profit
      p_max = max(p_max, p_cut)
   return p_max

rodLen = [7, 10]
profit = 6
cost = 4
print(solve(rodLen, profit, cost))

ইনপুট

[7, 10], 6, 4

আউটপুট

82