पायथन में फलों को अनुकूलित तरीके से भरने के लिए आवश्यक न्यूनतम लागत खोजने का कार्यक्रम

मान लीजिए कि हमारे पास फल नामक एक सूची है और अन्य दो मान k और कैप हैं। जहाँ प्रत्येक फल [i] के तीन मान हैं:[c, s, t], यह दर्शाता है कि प्रत्येक फल की कीमत 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, करें
  - fnum :=न्यूनतम तल (कैप / एस) और टी
  - यदि fnum 0 के समान है, तो
    - लूप से बाहर आएं
  - bnum :=t / fnum का तल
  - विकल्पों के अंत में ट्रिपलेट (कैप - fnum * s, fnum * c, bnum) डालें
  - t :=t - bnum * fnum
उत्तर:=0
विकल्पों की क्रमबद्ध सूची में प्रत्येक ट्रिपल (बाएं_कैप, बीकॉस्ट, बीएनयूएम) के लिए, करें
- bfill :=न्यूनतम k और bnum
- उत्तर:=उत्तर + बीकॉस्ट * बीफिल
- 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