Pythonで天秤とべき乗の重りを使って物品の重さを測定できるか判定する方法

この記事では、整数 a のべき乗で表される重り（a⁰, a¹, a², …, a¹⁰⁰）と、両側に重りを載せられる天秤を使って、重さ W の物品を測定できるかどうかを Python で判定する方法を解説します。

問題の概要

重りは天秤の左右どちら側にも置くことができます。つまり、各重りについて「使わない」「物品と同じ側に置く（引く）」「反対側に置く（足す）」の3つの選択肢があります。

例えば、a = 4、W = 17 の場合を考えてみましょう。利用できる重りは a⁰ = 1、a¹ = 4、a² = 16 です。16 + 1 = 17 となるため、出力は True になります。

解法のアプローチ

この問題は、各重りの3通りの使い方を全て試す全探索（バックトラッキング）で解けます。手順は以下の通りです。

• フラグ found を False で初期化します。
• 再帰関数 util(idx, itemWt, weights, N) を定義します。
  • found が True なら処理を打ち切ります。
  • 残りの重さ itemWt が 0 になれば、found を True にして終了します。
  • idx が重りの総数 N を超えたら戻ります。
  • それ以外の場合、次の3パターンを再帰的に呼び出します。
    • その重りを使わない：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 を返します（2進法・3進法の性質により任意の重さが表現できるため）。
  • サイズ 100 のリスト weights を用意し、weights[0] = 1 から順に a を掛けて重りを生成します。値が 10⁷ を超えたらループを抜けます。
  • util(0, W, weights, total_weights) を呼び出し、found の結果を返します。

実装例

それでは、実際の Python コードを見てみましょう。

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
    found = False
    # a が 2 または 3 の場合は必ず測定可能
    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))

入力

a = 4, W = 17

出力

True

計算量について

各重りに対して3通りの選択肢があるため、時間計算量は O(3^N) となります。ただし、答えが見つかった時点で探索を打ち切る枝刈り（found フラグによる早期リターン）を入れることで、多くのケースで実際の探索範囲を大幅に削減できます。