পাইথনে একটি ব্যাগে আইটেম ধরে রেখে আমরা সর্বাধিক মূল্য পেতে পারি

ধরুন আমাদের কাছে সংখ্যার দুটি তালিকা আছে। একটিকে ওজন বলা হয় এবং অন্যটিকে মান বলা হয়। এগুলি একই দৈর্ঘ্যের, আমাদের কাছে ক্ষমতা এবং গণনা নামে দুটি মান রয়েছে। এখানে ওজন[i] এবং মান [i] ith আইটেমের ওজন এবং মানকে প্রতিনিধিত্ব করে। আমরা সর্বাধিক ক্ষমতার ওজন ধরে রাখতে পারি এবং মোট আইটেমগুলি সর্বাধিক গণনা করতে পারি, এবং আমরা প্রতিটি আইটেমের একটি মাত্র কপি নিতে পারি, তাই আমাদের সর্বোচ্চ পরিমাণ মূল্য পেতে হবে।

সুতরাং, যদি ইনপুটটি ওজনের মত হয় =[2, 2, 4, 6] মান =[15, 15, 20, 35] ক্ষমতা =8 গণনা =3, তাহলে আউটপুট 50 হবে, যেমন আমরা প্রথম 3টি আইটেম নির্বাচন করতে পারি , যেহেতু মোট ওজন 8।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• আইটেম :=ওজন এবং মান গ্রহণ করে জোড়ার একটি তালিকা

• একটি ফাংশন dp() সংজ্ঞায়িত করুন। এটি i, cp, ct

  লাগবে

• যদি i আইটেমগুলির আকারের সমান হয় বা ct 0 এর সমান হয়, তাহলে

  • রিটার্ন 0.0

• (w, v) :=আইটেম[i]

• উত্তর :=dp(i + 1, cp, ct)

• যদি cp> =w, তাহলে

  • উত্তর :=সর্বাধিক উত্তর, dp(i + 1, cp - w, ct - 1) + v

• উত্তর ফেরত দিন

• মূল পদ্ধতি থেকে dp(0, ক্ষমতা, গণনা)

  রিটার্ন করুন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -

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

আউটপুট

50