পাইথনে স্কেল এবং কিছু ওজন ব্যবহার করে আইটেম পরিমাপ করা যায় কিনা তা পরীক্ষা করুন

ধরুন আমাদের কিছু ওজন আছে যেমন 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