Kiểm tra cân được vật trọng lượng W bằng cân lưỡng bàn và trọng lượng a^i (Python)

Bài toán: Có cân lưỡng bàn (đặt trọng lượng cả hai bên) và bộ trọng lượng a^0, a^1, ..., a^100. Kiểm tra có cân được vật trọng lượng W không.

Quan sát

Mỗi trọng lượng có 3 trạng thái: bên trái (-), bên phải (+), không dùng (0).
Tổng trọng lượng hiệu quả = tổng có dấu ±. Cần tìm tổ hợp dấu sao cho tổng = W.
Đặc biệt: nếu a = 2 hoặc 3, luôn cân được mọi W (hệ nhị phân cân bằng / balanced ternary).

Triển khai Python (Backtracking)

found = False

def util(idx, itemWt, weights, N):
    global found
    if found:
        return
    if itemWt == 0:
        found = True
        return
    if idx > N:
        return
    # 3 nhánh: không dùng, đặt bên phải (+), đặt bên trái (-)
    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
    weights[0] = 1
    total_weights = 0
    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)
    return found

# Test
print(solve(4, 17))  # True: 16 + 1 = 17 (4^2 + 4^0)

Kết quả

True

Giải thích

• Backtracking thử 3 lựa chọn cho mỗi trọng lượng.
• Cắt tỉa: nếu a=2 hoặc 3 trả về True ngay (định lý toán học).
• Giới hạn trọng lượng 10^7 để tránh vô hạn.
• Độ phức tạp worst-case: O(3^N) nhưng N nhỏ do giới hạn trọng lượng.