ধরুন আমাদের একটি সংখ্যা লক্ষ্য আছে। আমাদের আরও দুটি সংখ্যা A এবং B আছে। আমরা যতবার চাই ততবার A এবং B যোগ করে আমরা লক্ষ্য পেতে পারি কিনা তা পরীক্ষা করতে হবে।
সুতরাং, যদি ইনপুট টার্গেট =26 A =5 B =7 এর মত হয়, তাহলে আউটপুটটি True হবে কারণ আমরা A এবং B এর মতো (7 + 7 + 7 + 5) যোগ করে 26 পেতে পারি।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- একটি ফাংশন util() সংজ্ঞায়িত করুন। এটি x, a, b, is_ok, target লাগবে
- যদি x> টার্গেট, তারপর
- প্রত্যাবর্তন
- যদি is_ok[x] সত্য হয়, তাহলে
- প্রত্যাবর্তন
- is_ok[x] :=সত্য
- util(x + a, a, b, is_ok, target)
- util(x + b, a, b, is_ok, target)
- প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
- is_ok :=আকারের একটি অ্যারে (লক্ষ্য + 1) এবং False দিয়ে পূরণ করুন
- util(0, a, b, is_ok, target)
- রিটার্ন is_ok[target]
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
def util(x, a, b, is_ok, target): if x > target: return if is_ok[x]: return is_ok[x] = True util(x + a, a, b, is_ok, target) util(x + b, a, b, is_ok, target) def solve(target, a, b): is_ok = [False] * (target + 1) util(0, a, b, is_ok, target) return is_ok[target] target = 26 A = 5 B = 7 print(solve(target, A, B))
ইনপুট
26, 5, 7
আউটপুট
True
