পাইথনে অপ্টিমাইজড উপায়ে ফল পূরণের জন্য প্রয়োজনীয় ন্যূনতম খরচ খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের কাছে ফল নামক একটি তালিকা আছে এবং আরও দুটি মান k এবং ক্যাপ আছে। যেখানে প্রতিটি ফলের [i] তিনটি মান রয়েছে:[c, s, t], এটি নির্দেশ করে ফল i প্রতিটির দাম c, তাদের প্রতিটির আকার s, এবং তাদের মোট t আছে। k ধারণক্ষমতার ক্যাপের ফলের ঝুড়ির সংখ্যা উপস্থাপন করে। আমরা এই ক্রমে −

• প্রতিটি ঝুড়িতে শুধুমাত্র একই ধরনের ফল রাখা যায়
• প্রতিটি ঝুড়ি যতটা সম্ভব পূর্ণ হওয়া উচিত
• প্রতিটি ঝুড়ি যতটা সম্ভব সস্তা হওয়া উচিত

তাই যতটা সম্ভব ঝুড়ি পূরণ করার জন্য আমাদের ন্যূনতম খরচ খুঁজে বের করতে হবে।

সুতরাং, ইনপুট যদি ফলের মত হয় =[[5, 2, 3], [6, 3, 2], [2, 3, 2]] k =2 ক্যাপ =4, তাহলে আউটপুট হবে 12, কারণ আমরা দুটি ফল 0 সেকেন্ড নিতে পারে কারণ এই দুটি দিয়ে, আমরা প্রথম ঝুড়িটি মোট আকার 2+2=4 এর জন্য পূর্ণ করতে পারি, এর দাম 5+5=10। তারপর, আমরা ফল 2 এর একটি ব্যবহার করি কারণ এটি সস্তা। এর দাম 2 ইউনিট।

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

• বিকল্প :=একটি নতুন তালিকা
• ফলের প্রতিটি ট্রিপলেটের (c, s, t) জন্য, করুন
  • যখন t> 0, do
    • fnum :=ন্যূনতম মেঝে (cap/s) এবং t
    • যদি fnum 0 এর মত হয়, তাহলে
      • লুপ থেকে বেরিয়ে আসুন
    • bnum :=t / fnum এর তল
    • বিকল্পের শেষে ট্রিপলেট (ক্যাপ - fnum * s, fnum * c, bnum) সন্নিবেশ করুন
    • t :=t - bnum * fnum
• উত্তর :=0
• অপশনের সাজানো তালিকায় প্রতিটি ট্রিপলেটের জন্য (বাম_ক্যাপ, bcost, bnum) করুন
  • bfill :=ন্যূনতম k এবং bnum
  • উত্তর :=ans + bcost * bfill
  • k :=k - bfill
  • যদি k 0 এর সমান হয়, তাহলে
    • লুপ থেকে বেরিয়ে আসুন
• উত্তর ফেরত দিন

উদাহরণ

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

def solve(fruits, k, cap):
   options = []
   for c, s, t in fruits:
      while t > 0:
         fnum = min(cap // s, t)
         if fnum == 0:
            break
         bnum = t // fnum

         options.append((cap - fnum * s, fnum * c, bnum))
         t -= bnum * fnum
   ans = 0
   for left_cap, bcost, bnum in sorted(options):
      bfill = min(k, bnum)
      ans += bcost * bfill
      k -= bfill
      if k == 0:
         break

   return ans

fruits = [[5, 2, 3],[6, 3, 2],[2, 3, 2]]
k = 2
cap = 4
print(solve(fruits, k, cap))

ইনপুট

[[5, 2, 3],[6, 3, 2],[2, 3, 2]], 2, 4

আউটপুট

12