পাইথনে একাধিক কপি নেওয়ার মাধ্যমে আমরা ন্যাপস্যাক সমস্যায় পেতে পারি সর্বাধিক মান খুঁজে বের করার জন্য প্রোগ্রাম

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

সুতরাং, যদি ইনপুট হয় ওজন =[1, 2, 3], মান =[1, 5, 3], ক্ষমতা =5, তাহলে আউটপুট হবে 11

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

একটি ফাংশন dp() সংজ্ঞায়িত করুন। এর জন্য i, k
যদি আমি ওজনের আকারের সমান হয়, তাহলে
- রিটার্ন 0
উত্তর :=dp(i + 1, k)
যদি k>=ওজন[i], তাহলে
- উত্তর :=সর্বাধিক উত্তর এবং dp(i, k - ওজন[i]) + মান[i]
উত্তর ফেরত দিন
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
রিটার্ন ডিপি(0, ক্ষমতা)

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

উদাহরণ

class Solution:
   def solve(self, weights, values, capacity):
      def dp(i, k):
         if i == len(weights):
            return 0
         ans = dp(i + 1, k)
         if k >= weights[i]:
            ans = max(ans, dp(i, k - weights[i]) + values[i])
         return ans
      return dp(0, capacity)
ob = Solution()
weights = [1, 2, 3]
values = [1, 5, 3]
capacity = 5
print(ob.solve(weights, values, capacity))

ইনপুট

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