পাইথনে লেবেল থেকে সর্বোচ্চ ভ্যালু বের করুন

একটি আইটেম সেট দেওয়া আছে: i-তম আইটেমের ভ্যালু values[i] এবং লেবেল labels[i]। একটি সাবসেট S নিতে হবে যাতে:

|S| <= num_wanted
প্রতিটি লেবেল L-এর জন্য, S-এ লেবেল L-যুক্ত আইটেমের সংখ্যা <= use_limit

সাবসেট S-এর সর্বোচ্চ সম্ভাব্য যোগফল বের করতে হবে।

values = [5,4,3,2,1], labels = [1,1,2,2,3], num_wanted = 3, use_limit = 1 হলে আউটপুট 9। কারণ প্রথম, তৃতীয় এবং পঞ্চম আইটেম বেছে নেওয়া হয়েছে।

সমাধানের ধাপসমূহ

v নামের একটি অ্যারে তৈরি করুন
values এর দৈর্ঘ্য পর্যন্ত লুপে [values[i], labels[i]] v-তে ইনসার্ট করুন
v অ্যারেটি সর্ট করুন (ডিসেন্ডিং)
ans := 0, use := খালি ম্যাপ, i := 0
যখন num_wanted > 0 এবং i < len(v):
- যদি v[i][1] use-এ নেই: num_wanted--, ans += v[i][0], use[v[i][1]] = 1
- অথবা use[v[i][1]] < use_limit: num_wanted--, ans += v[i][0], use[v[i][1]]++
- i++
ans রিটার্ন করুন

উদাহরণ

class Solution(object):
    def largestValsFromLabels(self, values, labels, num_wanted, use_limit):
        v = []
        for i in range(len(values)):
            v.append([values[i], labels[i]])
        v = sorted(v, key=lambda v: v[0], reverse=True)
        ans = 0
        use = {}
        i = 0
        while num_wanted and i < len(v):
            if v[i][1] not in use:
                num_wanted -= 1
                ans += v[i][0]
                use[v[i][1]] = 1
            elif use[v[i][1]] < use_limit:
                num_wanted -= 1
                ans += v[i][0]
                use[v[i][1]] += 1
            i += 1
        return ans

ob = Solution()
print(ob.largestValsFromLabels([5,4,3,2,1], [1,1,2,2,3], 3, 1))

ইনপুট

[5,4,3,2,1] [1,1,2,2,3] 3 1