ট্রাকে সর্বাধিক ইউনিট লোড করার প্রোগ্রাম

boxTypes ২D অ্যারে দেওয়া আছে, boxTypes[i] = [বক্সের সংখ্যা, প্রতি বক্সে ইউনিট সংখ্যা]। ট্রাকে সর্বোচ্চ kটি বক্স লোড করা যাবে। সর্বাধিক মোট ইউনিট লোড করতে হবে।

ইনপুট: boxTypes = [[2,4],[3,3],[4,2]], k = 6 → আউটপুট: 19। টাইপ ১ (২ বক্স × ৪ ইউনিট) + টাইপ ২ (৩ বক্স × ৩ ইউনিট) + টাইপ ৩ (১ বক্স × ২ ইউনিট) = ৮+৯+২=১৯।

সমাধানের ধাপসমূহ (লালচী পদ্ধতি / Greedy)

boxTypes-কে প্রতি বক্স ইউনিট সংখ্যা অনুযায়ী ডিসেন্ডিং সর্ট করুন
total := 0, fill := 0
প্রতিটি i ∈ boxTypes-এর জন্য:
- যদি fill + i[0] <= k: fill += i[0], total += i[0]*i[1]
- অন্যথায়: total += (k - fill) * i[1], break
total রিটার্ন করুন

উদাহরণ (Python)

def solve(boxTypes, k):
    boxTypes.sort(key=lambda x: x[1], reverse=True)
    total = 0
    fill = 0
    for i in boxTypes:
        if fill + i[0] <= k:
            fill += i[0]
            total += i[0] * i[1]
        else:
            total += (k - fill) * i[1]
            break
    return total

boxTypes = [[2,4],[3,3],[4,2]]
k = 6
print(solve(boxTypes, k))

ইনপুট

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