用 Python 编写程序来查找最接近的甜点价格

pythonserver side programmingprogramming更新于 2025/12/2 2:20:17

假设我们有两个数组，分别为 baseCosts 和 toppingCosts，前者有 n 个项目，我们可以从中选择底料，后者有 m 个项目，我们可以从中选择配料，并且还有一个目标值。我们必须遵循这些规则来制作甜点。

必须只有一个底料。
我们可以添加一种或多种配料，或者根本没有配料。
每种配料最多有两个。

这里 baseCosts[i] 表示第 i 种冰淇淋底料的价格。toppingCosts[i] 表示第 i 种配料之一的价格。目标值表示甜点的目标价格。我们必须制作总成本尽可能接近目标的甜点。我们必须找到最接近目标的甜点成本。如果有多个答案，则返回较低的答案。

因此，如果输入为 baseCosts = [2,8]、toppingCosts = [4,5]、target = 12，则输出将为 12，因为我们可以取成本为 8 的 base，然后取成本为 4 的第一个配料中的 1 个，并且没有 type2 配料，因此总成本为 8+4 = 12。

为了解决这个问题，我们将遵循以下步骤 −

best_cost := baseCosts[0]
对于 b，范围为 0 到 baseCosts 的大小 - 1，执行
- bitmask := 一个大小与 toppingCosts 大小相同的数组，并用 0 填充
- 无限次执行以下操作，执行
  - current_price := baseCosts[b]
  - 对于 j，范围从 0 到位掩码大小 - 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
  - 如果 0 不在位掩码中且 1 不在位掩码中，则
    - 退出循环
  - 对于 i 在 0 到位掩码大小 - 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))