Giả sử chúng ta có một mục tiêu số. Chúng ta có hai số khác A và B. Chúng ta phải kiểm tra xem chúng ta có thể đạt được mục tiêu hay không bằng cách thêm A và B bao nhiêu lần tùy ý.
Vì vậy, nếu đầu vào là Target =26 A =5 B =7, thì đầu ra sẽ là True vì chúng ta có thể nhận được 26 bằng cách thêm A và B như (7 + 7 + 7 + 5).
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Xác định một hàm dùng (). Điều này sẽ lấy x, a, b, is_ok, target
- if x> target, then
- trở lại
- nếu is_ok [x] là True, thì
- trở lại
- is_ok [x]:=True
- use (x + a, a, b, is_ok, target)
- use (x + b, a, b, is_ok, target)
- Từ phương thức chính, hãy làm như sau -
- is_ok:=một mảng có kích thước (target + 1) và điền bằng False
- use (0, a, b, is_ok, target)
- return is_ok [target]
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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))
Đầu vào
26, 5, 7
Đầu ra
True