ধরুন আমাদের কিছু ওজন আছে যেমন a^0, a^1, a^2, …, a^100, এখানে 'a' একটি পূর্ণসংখ্যা, এবং আমাদের একটি ওজনের স্কেলও রয়েছে যেখানে ওজনগুলি এর উভয় পাশে রাখা যেতে পারে। স্কেল. এই ওজনগুলি ব্যবহার করে W ওজনের একটি নির্দিষ্ট আইটেম পরিমাপ করা যায় কিনা তা আমাদের পরীক্ষা করতে হবে।
সুতরাং, যদি ইনপুটটি a =4, W =17 এর মত হয়, তাহলে আউটপুটটি True হবে ওজন a^0 =1, a^1 =4, a^2 =16, আমরা পেতে পারি 16 + 1 =17 .
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- পাওয়া :=মিথ্যা
- একটি ফাংশন util() সংজ্ঞায়িত করুন। এটি idx, itemWt, ওজন, N লাগবে
- যদি পাওয়া যায় সত্য, তারপর
- প্রত্যাবর্তন
- যদি itemWt 0 এর মত হয়, তাহলে
- পাওয়া :=সত্য
- প্রত্যাবর্তন
- যদি idx> N হয়, তাহলে
- প্রত্যাবর্তন
- util(idx + 1, itemWt, weights, N)
- util(idx + 1, itemWt + weights[idx], weights, N)
- util(idx + 1, itemWt - ওজন[idx], ওজন, N)
- প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
- যদি a 2 বা 3 হয়, তাহলে
- সত্য ফেরান
- ওজন :=100 আকারের একটি তালিকা এবং 0 দিয়ে পূরণ করুন
- মোট_ওজন :=0
- ওজন[0] :=1, i :=1
- নিম্নলিখিতটি অসীমভাবে করুন, করুন
- ওজন[i] :=ওজন[i - 1] * a
- মোট_ওজন :=মোট_ওজন + 1
- যদি ওজন হয়[i]> 10^7
- লুপ থেকে বেরিয়ে আসুন
- i :=i + 1
- util(0, W, weights, total_weights)
- যদি সত্য পাওয়া যায়, তাহলে
- সত্য ফেরান
- মিথ্যে ফেরত দিন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
found = False def util(idx, itemWt, weights, N): global found if found: return if itemWt == 0: found = True return if idx > N: return util(idx + 1, itemWt, weights, N) util(idx + 1, itemWt + weights[idx], weights, N) util(idx + 1, itemWt - weights[idx], weights, N) def solve(a, W): global found if a == 2 or a == 3: return True weights = [0] * 100 total_weights = 0 weights[0] = 1 i = 1 while True: weights[i] = weights[i - 1] * a total_weights += 1 if weights[i] > 10**7: break i += 1 util(0, W, weights, total_weights) if found: return True return False a = 4 W = 17 print(solve(a, W))
ইনপুট
4, 17
আউটপুট
True