ধরুন আমাদের একটি অ্যারে আছে যার নাম nums এবং আরেকটি মান সমষ্টি। সংখ্যায় উপস্থিত উপাদান যোগ করে যোগফল পাওয়া সম্ভব কিনা তা আমাদের পরীক্ষা করতে হবে, আমরা একাধিকবার একটি একক উপাদান বাছাই করতে পারি।
সুতরাং, যদি ইনপুটটি nums =[2, 3, 5] sum =28 এর মত হয়, তাহলে আউটপুটটি True হবে কারণ আমরা 5 + 5 + 5 + 5 + 3 + 3 + 2 ব্যবহার করে 26 পেতে পারি
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- MAX :=1000
- টেবিল :=0 দিয়ে MAX বিজ্ঞাপন পূরণের একটি অ্যারে
- একটি ফাংশন util() সংজ্ঞায়িত করুন। এটি সংখ্যা লাগবে
- টেবিল[0] :=1
- তালিকা সংখ্যা সাজান
- আমি 0 থেকে সংখ্যার আকার - 1 এর মধ্যে, কর
- val :=সংখ্যা[i]
- যদি টেবিল[val] অ-শূন্য হয়, তাহলে
- পরবর্তী পুনরাবৃত্তির জন্য যান
0 থেকে MAX - val - 1 এর মধ্যে j-এর জন্য - করুন
- যদি টেবিল[j] অ-শূন্য হয়, তাহলে
- টেবিল[j + val] :=1
- যদি টেবিল[j] অ-শূন্য হয়, তাহলে
- প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
- util(সংখ্যা)
- যদি টেবিল[সমষ্টি] অ-শূন্য হয়, তাহলে
- সত্য ফেরান
- মিথ্যে ফেরত দিন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
MAX = 1000 table = [0] * MAX def util(nums): table[0] = 1 nums.sort() for i in range(len(nums)): val = nums[i] if table[val]: continue for j in range(MAX - val): if table[j]: table[j + val] = 1 def solve(nums, sum): util(nums) if table[sum]: return True return False nums = [2, 3, 5] sum = 28 print (solve(nums, sum))
ইনপুট
[2, 3, 5], 28
আউটপুট
True