มีน้ำหนัก a^0, a^1, ..., a^100 (a เป็น Integer) และ Scale ที่วางน้ำหนักได้ทั้งสองข้าง ต้องตรวจสอบว่าวัดน้ำหนัก W ได้หรือไม่
เช่น Input a = 4, W = 17 Output True เพราะ 1 + 16 = 17 (a^0 + a^2)
ขั้นตอนแก้ (Backtracking):
- ถ้า a = 2 หรือ 3 Return True (ทุกจำนวนแทนได้)
- สร้าง List Weights จนเกิน 10^7
- DFS ลอง 3 ทาง: ไม่นำ, ใส่ข้าง Item, ใส่ข้างตรงข้าม (Backtracking)
ตัวอย่างโค้ด
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))
Input
4, 17
Output
True
