পাইথনে বস্তু ব্যাগে রাখে সর্বোচ্চ মূল্য উপার্জন

ধরুন, weights এবং values নামক দুটি সমান দৈর্ঘ্যের তালিকা দেওয়া আছে। weights[i] এবং values[i] যথাক্রমে i-তম বস্তুর ওজন এবং মান। আমাদের কাছে capacity ওজন এবং count সংখ্যক বস্তু রাখার সীমা রয়েছে। প্রতিটি বস্তুর একটি কপি মাত্র নেওয়া যায়। লক্ষ্য হল সর্বোচ্চ মোট মান উপার্জন করা।

উদাহরণ: weights = [2, 2, 4, 6], values = [15, 15, 20, 35], capacity = 8, count = 3 হলে আউটপুট ৫০, কারণ প্রথম তিনটি বস্তু বেছে নিলে মোট ওজন ৮ হয়।

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

items := weights এবং values জোড়া করুন
dp(i, cp, ct) ফাংশন সংজ্ঞায়িত করুন:
- যদি i == len(items) বা ct == 0 হয়, তবে 0.0 ফেরত দিন
- (w, v) := items[i]
- ans := dp(i+1, cp, ct)
- যদি cp >= w হয়, তবে ans := max(ans, dp(i+1, cp-w, ct-1) + v)
- ans ফেরত দিন
মূল ফাংশন থেকে dp(0, capacity, count) ফেরত দিন

উদাহরণ কোড

class Solution:
    def solve(self, weights, values, capacity, count):
        items = list(zip(weights, values))
        def dp(i, cp, ct):
            if i == len(items) or ct == 0:
                return 0.0
            w, v = items[i]
            ans = dp(i + 1, cp, ct)
            if cp >= w:
                ans = max(ans, dp(i + 1, cp - w, ct - 1) + v)
            return ans
        return int(dp(0, capacity, count))

ob = Solution()
weights = [2, 2, 4, 6]
values = [15, 15, 20, 35]
capacity = 8
count = 3
print(ob.solve(weights, values, capacity, count))

ইনপুট

[2, 2, 4, 6], [15, 15, 20, 35], 8, 3