สมมุติว่าเรามีเป้าหมายเป็นตัวเลข เรามีเลข A กับ B อีกสองตัว เราต้องเช็คก่อนว่าจะได้เป้าไหมโดยเติม A กับ B กี่รอบก็ได้
ดังนั้น หากอินพุตเป็นเหมือน Target =26 A =5 B =7 ผลลัพธ์จะเป็น True เนื่องจากเราจะได้ 26 โดยการเพิ่ม A และ B เช่น (7 + 7 + 7 + 5)
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดฟังก์ชัน util() นี่จะใช้เวลา x, a, b, is_ok, เป้าหมาย
- ถ้า x> เป้าหมาย แล้ว
- คืนสินค้า
- ถ้า is_ok[x] เป็น True แล้ว
- คืนสินค้า
- is_ok[x] :=จริง
- util(x + a, a, b, is_ok, target)
- util(x + b, a, b, is_ok, เป้าหมาย)
- จากวิธีหลัก ให้ทำดังนี้ -
- is_ok :=อาร์เรย์ขนาด (เป้าหมาย + 1) และเติมด้วย False
- util(0, a, b, is_ok, เป้าหมาย)
- ส่งคืน is_ok[เป้าหมาย]
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def util(x, a, b, is_ok, target): if x > target: return if is_ok[x]: return is_ok[x] = True util(x + a, a, b, is_ok, target) util(x + b, a, b, is_ok, target) def solve(target, a, b): is_ok = [False] * (target + 1) util(0, a, b, is_ok, target) return is_ok[target] target = 26 A = 5 B = 7 print(solve(target, A, B))
อินพุต
26, 5, 7
ผลลัพธ์
True
