Python中的查找最接近甜点成本的程序

假设我们有两个数组，一个称为baseCosts有n个条目，我们可以选择一个基础，另一个称为toppingCosts有m个条目，我们可以从中选择配料，并且还有一个目标值。我们必须遵循以下规则制作甜点。

必须恰好有一个基础。
我们可以添加一个或多个配料，也可以根本没有配料。
每种类型的配料最多只有两种。

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

因此，如果输入如baseCosts = [2, 8]，toppingCosts = [4, 5]，target = 12，则输出将为12，因为我们可以采用成本为8的基础，然后采用成本为4的第一种配料，没有第二种配料，因此总成本为8 + 4 = 12。

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

best_cost := baseCosts [0]
for b in range 0 to size of baseCosts – 1, do
- bitmask:=一个大小与toppingCosts大小相同的数组，填充0
- 无限做以下操作
  - current_price:=baseCosts [b]
  - for j in range 0 to size of bitmask-1, do
  - current_price:=current_price+bitmask[j]*toppingCosts[j]
  - 如果当前价格-目标与0相同，则
  - 返回目标
  - 否则，当| 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和1，则
  - 退出循环
  - for i in range 0 to size of bitmask-1, do
  - 如果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))