比特卡在寻找极限下的最大可能值

Question

def prescribe(d, a, b):

尝试给定目标数字 d，例如 4540，我想计算数字 a（例如 9）在不超过该值的情况下可以达到多近。除了一堆其他标准。这是我到目前为止创建的作品：

sum = 0
x = int(d / a) * a
y = int(d / b) * b

if d % a == 0:
    return x
elif d % b == 0:
    return y
while d > sum:
    sum += a + b
final = sum - (a + b)

if x > final and x > y:
    return x
elif y > final and y > sum:
    return y
else:
    return final

诚然，这不是最有效的代码，所以请耐心等待。这里发生的主要问题是我似乎不太明白如何 return 目标 d 内的最大可能值。因此，例如当我使用以下参数调用函数时：

prescribe(4540, 9, 15)

我return的最大值是数字9：4536，而实际上答案是4539。我假设的问题是我通过简单地将 4540 除以 9，然后使用 int() 函数将 504.4 转换为 504.0 来获得最大可能值。实际上我应该使用 504.3.

我希望这能说明我的代码所面临的缺点 — 似乎无法弄清楚如何才能在目标范围内获得最大可能值。如果有人可以就我应该处理的限制或方式向我提出建议，我将不胜感激。

Answer 1

一串解法

def prescribe(d, a, b):
    return d - min((d - a * i) % b for i in range(d // a + 1))


print(prescribe(4540, 9, 15))  # 4539

说明

所以让我们将此任务改写为

找到 a*x + b*y + r = d 的最小 r，其中 d、a、b 是给定参数，x、y 是变量

解决方案是

您必须遍历所有可能的 x（或 y），但只要 a 为正，您只需遍历 [0, d//a] 间隔。
计数r = (d - a * x) % b
找到您收到的所有 r 之间的最小值

比特卡在寻找极限下的最大可能值

Bit stuck on finding the largest possible value under a limit

python

algorithm

logic

function