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, 가중치, N)
- util(idx + 1, itemWt + weights[idx], weights, N)
- util(idx + 1, itemWt - 가중치[idx], 가중치, N)
- 메인 방법에서 다음을 수행하십시오 -
- a가 2 또는 3이면
- 참 반환
- weights :=크기가 100이고 0으로 채워지는 목록
- total_weights :=0
- 가중치[0] :=1, 나는 :=1
- 무한하게 다음을 수행합니다
- 가중치[i] :=가중치[i - 1] * a
- total_weights :=total_weights + 1
- 가중치[i]> 10^7
- 인 경우
- 루프에서 나오다
- 나는 :=나는 + 1
- util(0, W, weights, total_weights)
- 사실이면
- 참 반환
- 거짓을 반환
예
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
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