数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Python 程序查找最接近的甜点成本
假设我们有两个数组，称为 baseCosts，其中包含 n 个项目，我们可以从中选择基础，toppingCosts，其中包含 m 个项目，我们可以从中选择浇头，并且还有一个目标值。我们必须遵循以下规则来制作甜点。
必须恰好有一个基础。
我们可以添加一个或多个浇头，或者根本不添加浇头。
每种浇头的数量最多为两个。
这里 baseCosts[i] 表示第 i 个冰淇淋基础的价格。toppingCosts[i] 表示第 i 个浇头的价格。目标值表示甜点的目标价格。我们必须制作一个总成本尽可能接近目标的甜点。我们必须找到甜点最接近目标的可能成本。如果有多个答案，则返回较小的那个。
因此，如果输入类似于 baseCosts = [2,8]，toppingCosts = [4,5]，target = 12，则输出将为 12，因为我们可以选择成本为 8 的基础，然后选择成本为 4 的第一个浇头 1 个，并且不选择类型 2 的浇头，所以总成本为 8+4 = 12。
为了解决这个问题，我们将遵循以下步骤 -
best_cost := baseCosts[0]
对于 b 从 0 到 baseCosts 大小 - 1，执行
bitmask := 一个大小与 toppingCosts 大小相同的数组，并用 0 填充
无限循环执行以下操作：
current_price := baseCosts[b]
对于 j 从 0 到 bitmask 大小 - 1，执行
current_price := current_price + bitmask[j] * toppingCosts[j]
如果 current_price - target 等于 0，则
返回 target
否则，当 |current_price - target| < |best_cost - target| 时，则
best_cost := current_price
否则，当 |current_price - target| 等于 |best_cost - target| 时，则
如果 current_price < best_cost，则
best_cost := current_price
如果 bitmask 中没有 0 且 bitmask 中没有 1，则
退出循环
对于 i 从 0 到 bitmask 大小 - 1，执行
如果 bitmask[i] 不等于 2，则
bitmask[i] := bitmask[i] + 1
退出循环
否则，
bitmask[i] := 0
返回 best_cost
示例
让我们看看以下实现以获得更好的理解 -
def solve(baseCosts, toppingCosts, target): best_cost = baseCosts[0] for b in range(len(baseCosts)): bitmask = [0] * len(toppingCosts) while True: current_price = baseCosts[b] for j in range(len(bitmask)): current_price += bitmask[j] * toppingCosts[j] if current_price - target == 0: return target elif abs(current_price - target) < abs(best_cost - target): best_cost = current_price elif abs(current_price - target) == abs(best_cost - target): if current_price < best_cost: best_cost = current_price if 0 not in bitmask and 1 not in bitmask: break for i in range(len(bitmask)): if bitmask[i] != 2: bitmask[i] += 1 break else: bitmask[i] = 0 return best_cost baseCosts = [2,8] toppingCosts = [4,5] target = 12 print(solve(baseCosts, toppingCosts, target))
输入
[2,8], [4,5], 12
输出
12
169 次查看
