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

মান ল করুন একই দৈর্ঘ্যের দুটি তালিকা weights এবং values, এবং আরেকটি মান capacity। weights[i] এবং values[i] i-তম আইটেমের ওজন এবং মান বোঝায়। আমরা hoogstens capacity ওজন নিতে পারি এবং প্রতিটি আইটেমের যেকোনো সংখ্যক কপি নিতে পারি। সর্বোচ্চ কতটুকু মান পাওয়া যায় তা খুঁজে বের করতে হবে।

যদি ইনপুট হয় weights = [1, 2, 3], values = [1, 5, 3], capacity = 5, তবে আউটপুট হবে ১১।

এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব:

একটি dp() ফাংশন সংজ্ঞায়িত করুন। এটি i, k গ্রহণ করবে।
যদি i == weights-এর আকার হয়, তবে ০ ফেরত দিন।
ans := dp(i + 1, k)
যদি k >= weights[i] হয়, তবে ans := max(ans, dp(i, k - weights[i]) + values[i])
ans ফেরত দিন।
মূল মেথড থেকে dp(0, capacity) ফেরত দিন।

বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন:

উদাহরণ

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