পাইথনে ফল আপ্টিমাইজড ভাবে বাস্কেটে ভরার ন্যূনতম খরচ গণনা করার প্রোগ্রাম

পাইথনে একটি ফলের লিস্ট fruits এবং দুটি ভ্যালু k (বাস্কেটের সংখ্যা) এবং cap (বাস্কেটের ধারনক্ষমতা) দেওয়া আছে। প্রতিটি fruits[i] = [c, s, t] বোঝায়: ফল i-এর দাম c, আকার s, এবং মোট উপলব্ধ t। বাস্কেটগুলো নিচের কনস্ট্রেইন্ট অনুযায়ী ভরা হবে (অগ্রাধিকার ক্রমে):

1. প্রতিটি বাস্কেটে শুধু এক টাইপের ফল থাকবে
2. প্রতিটি বাস্কেট যত δυναয় সম্ভব ভরা থাকবে
3. প্রতিটি বাস্কেট যত সম্ভব সস্তা হবে

আমাদের বের করতে হবে যত могуছে বাস্কেট ভরার ন্যূনতম খরচ।

উদাহরণ

ইনপুট: fruits = [[5, 2, 3], [6, 3, 2], [2, 3, 2]], k = 2, cap = 4

আউটপুট: 12

ব্যাখ্যা:

• ফল ০: আকার ২, দাম ৫, মোট ৩টি -> প্রতিটি বাস্কেটে ২টি ফল (২×২=৪=cap), খরচ ১০, ১টি বাস্কেট সম্ভব (৩//২=১), ১টি ফল বাকি
• ফল ২: আকার ৩, দাম ২, মোট ২টি -> ১টি বাস্কেটে ১টি ফল (১×৩=৩<৪), খরচ ২, ২টি বাস্কেট সম্ভব
• অপ্টিমাল: ফল ০ এর ১ বাস্কেট (খরচ ১০) + ফল ২ এর ১ বাস্কেট (খরচ ২) = মোট ১২

এলগরিদম

1. options = [] — প্রতিটি সম্ভাব্য বাস্কেট কনফিগারেশন স্টোর করবে
2. প্রতিটি ফল (c, s, t) এর জন্য:
   • যখন t > 0:
     • fnum = min(cap // s, t) — একটি বাস্কেটে मैক্স কতটি ফল যায়
     • যদি fnum == 0: ব্রেক (ফলটি বাস্কেটে ফিট হয় না)
     • bnum = t // fnum — কতটি পূর্ণ বাস্কেট বানানো যাবে
     • options.append((cap - fnum*s, fnum*c, bnum)) — (খালি স্পেস, বাস্কেট খরচ, বাস্কেট সংখ্যা)
     • t -= bnum * fnum — বাকি ফল
3. options সর্ট করুন (খালি স্পেস অর্ডমে, তারপর খরচ অর্ডমে — পাইথন টাপল সর্টিংয়ের কারণে)
4. ans = 0
5. সর্টেড options থেকে বাস্কেট পূরণ করুন যতক্ষণ k > 0:
   • bfill = min(k, bnum)
   • ans += bcost * bfill
   • k -= bfill
6. 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))  # Output: 12

ইনপুট

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

আউটপুট

12

কী পয়েন্ট

• options এ (waste, cost, count) স্টোর করা হয় — সর্টিংয়ের সময় কম waste (আরও ভরা বাস্কেট) আগে আসে, তারপর কম cost।
• while t > 0 লুপটি একই ফল থেকে একাধিক টাইপের বাস্কেট কনফিগারেশন তৈরি করতে পারে (যদি বাকি ফল থেকে আরও বাস্কেট বানানো যায়)।
• গ্রিডি স্ট্র্যাটেজি: সবচেয়ে কম waste বাড়ে, তারপর কম cost — এটি কনস্ট্রেইন্টের অগ্রাধিকার মেনে চলে।