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

मान लीजिए हमारे पास fruits नामक एक सूची है और दो अन्य मान k और cap हैं। जहां प्रत्येक fruits[i] के तीन मान होते हैं: [c, s, t], यह दर्शाता है कि फल i की लागत c है, प्रत्येक का आकार s है, और कुल t हैं। k फल टोकरियों की संख्या दर्शाता है जिनकी क्षमता cap है। हम निम्नलिखित प्रतिबंधों के क्रम में फल टोकरियों को भरना चाहते हैं:

प्रत्येक टोकरी केवल एक ही प्रकार के फल रख सकती है
प्रत्येक टोकरी यथासंभव भरी होनी चाहिए
प्रत्येक टोकरी यथासंभव सस्ती होनी चाहिए

इसलिए हमें अधिकतम टोकरियों को भरने के लिए आवश्यक न्यूनतम लागत ज्ञात करनी है।

इसलिए, यदि इनपुट है fruits = [[5, 2, 3], [6, 3, 2], [2, 3, 2]] k = 2 cap = 4, तो आउटपुट 12 होगा, क्योंकि हम फल 0 के दो ले सकते हैं क्योंकि इन दो के साथ, हम पहली टोकरी को कुल आकार 2+2=4 के लिए भर सकते हैं, इसकी लागत 5+5=10 है। फिर, हम फल 2 का एक उपयोग करते हैं क्योंकि यह सस्ता है। इसकी लागत 2 यूनिट है।

हल करने का दृष्टिकोण

options := एक नई सूची
fruits में प्रत्येक ट्रिपल (c, s, t) के लिए, करें:
- जब तक t > 0, करें:
  - fnum := min(cap // s, t) का फ्लोर
  - यदि fnum 0 के समान है, तो लूप से बाहर आएं
  - bnum := t // fnum का फ्लोर
  - ट्रिपल (cap - fnum * s, fnum * c, bnum) को options के अंत में डालें
  - t := t - bnum * fnum
ans := 0
options की क्रमबद्ध सूची में प्रत्येक ट्रिपल (left_cap, bcost, bnum) के लिए, करें:
- bfill := min(k, bnum)
- ans := ans + bcost * bfill
- k := k - bfill
- यदि k 0 के समान है, तो लूप से बाहर आएं
ans लौटाएं

उदाहरण

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