Giả sử chúng ta có một số quả cân như a ^ 0, a ^ 1, a ^ 2,…, a ^ 100, ở đây 'a' là một số nguyên và chúng ta cũng có một cái cân mà quả cân có thể được đặt ở cả hai mặt của nó. tỉ lệ. Chúng tôi phải kiểm tra xem một vật cụ thể có trọng lượng W có thể được đo bằng các trọng lượng này hay không.
Vì vậy, nếu đầu vào là a =4, W =17, thì đầu ra sẽ là Đúng với trọng số là a ^ 0 =1, a ^ 1 =4, a ^ 2 =16, chúng ta có thể nhận được 16 + 1 =17 .
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- tìm thấy:=Sai
- Xác định một hàm dùng (). Điều này sẽ lấy idx, itemWt, weights, N
- nếu tìm thấy là đúng, thì
- trở lại
- nếu itemWt giống 0, thì
- tìm thấy:=True
- trở lại
- nếu idx> N, thì
- trở lại
- use (idx + 1, itemWt, weights, N)
- use (idx + 1, itemWt + weights [idx], weights, N)
- use (idx + 1, itemWt - weights [idx], weights, N)
- Từ phương thức chính, hãy làm như sau -
- nếu a là 2 hoặc 3, thì
- trả về True
- weights:=danh sách kích thước 100 và điền bằng 0
- total_weights:=0
- trọng số [0]:=1, i:=1
- Thực hiện vô hạn những điều sau đây, hãy thực hiện
- weights [i]:=weights [i - 1] * a
- total_weights:=total_weights + 1
- nếu trọng số [i]> 10 ^ 7
- ra khỏi vòng lặp
- i:=i + 1
- use (0, W, weights, total_weights)
- nếu được tìm thấy đúng, thì
- trả về True
- trả về Sai
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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))
Đầu vào
4, 17
Đầu ra
True