जांचें कि क्या पायथन में एक पैमाने और कुछ वजन का उपयोग करके आइटम को मापा जा सकता है

मान लीजिए कि हमारे पास कुछ वज़न हैं जैसे a^0, a^1, a^2,…, a^100, यहाँ 'a' एक पूर्णांक है, और हमारे पास एक वजन पैमाना भी है जहाँ वज़न उसके दोनों ओर रखा जा सकता है पैमाना। हमें यह जांचना है कि W वजन की एक विशेष वस्तु को इन वजनों का उपयोग करके मापा जा सकता है या नहीं।

इसलिए, यदि इनपुट ए =4, डब्ल्यू =17 की तरह है, तो आउटपुट सही होगा वजन एक ^ 0 =1, ए ^ 1 =4, ए ^ 2 =16 है, हम 16 + 1 =17 प्राप्त कर सकते हैं ।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• मिला:=झूठा
• उपयोग() फ़ंक्शन को परिभाषित करें। यह idx, itemWt, weights, N
लेगा
• अगर सही पाया गया, तो
  • वापसी
• यदि आइटम डब्ल्यूटी 0 के समान है, तो
  • मिला :=सच
  • वापसी
• यदि idx> N, तो
  • वापसी
• उपयोग(idx + 1, itemWt, weight, N)
• उपयोग(idx + 1, itemWt + weights[idx], weight, N)
• उपयोग(idx + 1, itemWt - weights[idx], weight, N)
• मुख्य विधि से निम्न कार्य करें -
• यदि a या तो 2 या 3 है, तो
  • सही लौटें
• वजन :=आकार 100 की एक सूची और 0 से भरें
• कुल_वजन :=0
• वजन[0] :=1, i :=1
• निम्नलिखित को असीम रूप से करें, करें
  • वजन[i] :=वजन[i - 1] * a
  • total_weights :=Total_weights + 1
  • अगर वज़न[i]> 10^7
    • लूप से बाहर आएं
  • i :=i + 1
• उपयोग(0, डब्ल्यू, वजन, कुल वजन)
• अगर सही पाया गया, तो
  • सही लौटें
• झूठी वापसी

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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