检查是否可以使用 Python 中的秤和一些重量来测量项目
假设我们有一些权重，例如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.
示例
让我们看看以下实现以获得更好的理解-
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