পাইথনে ফ্র্যাকশন্যাল ন্যাপস্যাক সমস্যা বাস্তবায়নের প্রোগ্রাম

ধরা যাক weights এবং values নামক দুটি সমান দৈর্ঘ্যের তালিকা এবং একটি capacity মান আছে। weights[i] এবং values[i] i-তম আইটেমের ওজন ও মান। সর্বোচ্চ capacity ওজন নেওয়া যাবে এবং ভগ্নাংশে ওজন নিলে সমানুপাতিক মান मिलবে। ন্যূনতম পূর্ণসংখ্যা (floor) মান বের করতে হবে।

উদাহরণ: weights = [6, 7, 3], values = [110, 120, 2], capacity = 10 হলে আউটপুট 178 (কিন্তু প্রদত্ত কোডে আউটপুট 230 দেখানো হয়েছে, সম্ভবত উদাহরণে ভুল আছে)।

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

res := 0
P := (weight, value) জোড়ার তালিকা, value/weight অনুপাত অনুযায়ী ডিসেন্ডিং সর্ট করুন।
প্রতিটি জোড়া জন্য: যদি capacity == 0, ব্রেক করুন।

যদি weight > capacity: res += int(value / (weight / capacity)), capacity = 0
অন্যথায়: res += value, capacity -= weight

int(res) ফেরত দিন।

উদাহরণ কোড

class Solution:
    def solve(self, weights, values, capacity):
        res = 0
        for pair in sorted(zip(weights, values), key=lambda x: -x[1]/x[0]):
            if not bool(capacity):
                break
            if pair[0] > capacity:
                res += int(pair[1] / (pair[0] / capacity))
                capacity = 0
            elif pair[0] <= capacity:
                res += pair[1]
                capacity -= pair[0]
        return int(res)

ob = Solution()
weights = [6, 7, 3]
values = [110, 120, 2]
capacity = 10
print(ob.solve(weights, values, capacity))

ইনপুট

[6, 7, 3],[110, 120, 2],10