สมมติว่าเรามีตุ้มน้ำหนักเช่น 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 .
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- พบ :=เท็จ
- กำหนดฟังก์ชัน util() สิ่งนี้จะใช้ idx, itemWt, weights, N
- หากพบว่าเป็นจริง
- คืนสินค้า
- ถ้า itemWt เหมือนกับ 0 แล้ว
- พบ :=จริง
- คืนสินค้า
- ถ้า 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
- น้ำหนักรวม :=0
- น้ำหนัก[0] :=1, ผม :=1
- ทำสิ่งต่อไปนี้อย่างไม่สิ้นสุด ทำ
- weights[i] :=weights[i - 1] * a
- total_weights :=total_weights + 1
- ถ้า weights[i]> 10^7
- ออกมาจากลูป
- ผม :=ผม + 1
- util(0, W, weights, total_weights)
- หากพบว่าเป็นจริง
- คืนค่า True
- คืนค่าเท็จ
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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
