Pythonでスケールといくつかの重みを使用してアイテムを測定できるかどうかを確認します

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を取得できます。 。

これを解決するには、次の手順に従います-

• found：=False
• 関数util（）を定義します。これには、idx、itemWt、weights、Nが必要です
• 見つかった場合はtrue、
  • 戻る
• itemWtが0と同じ場合、
  • found：=True
  • 戻る
• idx> Nの場合、
  • 戻る
• util（idx + 1、itemWt、weights、N）
• util（idx + 1、itemWt + weights [idx]、weights、N）
• util（idx + 1、itemWt --weights [idx]、weights、N）
• メインの方法から次のようにします-
• aが2または3の場合、
  • Trueを返す
• weights：=サイズ100のリストで、0で埋めます
• total_weights：=0
• weights [0]：=1、i：=1
• 次のことを無限に行います。
  • weights [i]：=weights [i-1] * a
  • total_weights：=total_weights + 1
  • ウェイト[i]>10^7
    の場合
    • ループから抜け出す
  • i：=i + 1
• util（0、W、weights、total_weights）
• 真であることが判明した場合、
  • Trueを返す
• Falseを返す

例

理解を深めるために、次の実装を見てみましょう-

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