ধরুন আমাদের কাছে ওজন এবং মান নামে দুটি তালিকা রয়েছে যা একই দৈর্ঘ্যের এবং আরেকটি সংখ্যাকে বলা হয় ক্ষমতা k। এখানে ওজন[i] এবং মান [i] ith আইটেমের ওজন এবং মান দেখায়। এখন, আমরা সর্বাধিক k ধারণক্ষমতার ওজন নিতে পারি, এবং আমরা প্রতিটি আইটেমের সর্বাধিক একটি কপি নিতে পারি, আমাদের সর্বোচ্চ পরিমাণ মূল্য পেতে হবে।
সুতরাং, যদি ইনপুট হয় ওজন =[2, 3, 4], মান =[2, 6, 4], ক্ষমতা =6, তাহলে আউটপুট হবে 8
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- n:=ওজনের আকার
- dp:=আকার ক্ষমতা x n এর একটি ম্যাট্রিক্স, এবং 0 দিয়ে পূরণ করুন
- আমি 0 থেকে n রেঞ্জের জন্য, কর
- 0 থেকে ধারণক্ষমতার মধ্যে j-এর জন্য,
- যদি i 0 এর মত হয় বা j 0 এর মত হয়, তাহলে
- dp[i, j]:=0
- অন্যথায় যখন ওজন করা হয়[i-1] <=j, তারপর
- dp[i,j] =সর্বাধিক (dp[i-1, j-ওজন[i - 1]] + মান[i-1]) এবং (dp[i-1, j])
- অন্যথায়,
- dp[i, j]:=dp[i-1, j]
- করুন
- যদি i 0 এর মত হয় বা j 0 এর মত হয়, তাহলে
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
class Solution: def solve(self, weights, values, capacity): n=len(weights) dp=[[0 for i in range(capacity+1)] for _ in range(n+1)] for i in range(n+1): for j in range(capacity+1): if i==0 or j==0: dp[i][j]=0 elif weights[i-1]<=j: dp[i][j]=max(dp[i-1][j-weights[i-1]]+values[i-1],dp[i-1][j]) else: dp[i][j]=dp[i-1][j] return dp[n][capacity] ob = Solution() weights = [2, 3, 4] values = [2, 6, 4] capacity = 6 print(ob.solve(weights, values, capacity))
ইনপুট
[2, 3, 4], [2, 6, 4], 6
আউটপুট
8
