Python에서 가장 가까운 디저트 비용을 찾는 프로그램

<시간/>

n개의 항목이 있는 baseCost라는 두 개의 배열이 있다고 가정하고 base를 선택할 수 있고 m개의 항목이 있는 toppingCosts는 토핑을 선택하고 대상 값도 가질 수 있습니다. 디저트를 만들려면 이 규칙을 따라야 합니다.

정확히 하나의 베이스가 있어야 합니다.
하나 이상의 토핑을 추가하거나 토핑을 전혀 추가하지 않을 수 있습니다.
각 토핑 유형은 최대 2개입니다.

여기서 baseCosts[i]는 i번째 아이스크림 베이스의 가격을 나타냅니다. toppingCosts[i]는 i번째 토핑 중 하나의 가격을 나타냅니다. 목표 값은 디저트의 목표 가격을 나타냅니다. 최대한 목표에 가까운 총비용으로 디저트를 만들어야 한다. 우리는 타겟에 가장 가까운 디저트 비용을 찾아야 합니다. 답변이 여러 개인 경우 낮은 답변을 반환합니다.

따라서 입력이 baseCosts =[2,8], toppingCosts =[4,5], target =12와 같으면 비용이 8인 기본을 취한 다음 비용이 있는 첫 번째 토핑 중 1을 취할 수 있기 때문에 출력은 12가 됩니다. 4, type2 토핑이 없으므로 총 비용은 8+4 =12입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

best_cost :=baseCosts[0]
범위 0에서 baseCosts - 1까지의 b에 대해 수행
- bitmask :=toppingCosts의 크기와 크기가 같고 0으로 채워지는 배열
- 다음을 무한히 수행하십시오.
  - current_price :=기본 비용[b]
  - 범위 0에서 비트마스크 크기 - 1까지의 j에 대해
    - current_price :=current_price + bitmask[j] * toppingCosts[j]
  - current_price - target이 0인 경우
    - 반환 대상
  - 그렇지 않으면 |current_price - target| <|best_cost - target| 다음
    - best_cost :=current_price
  - 그렇지 않으면 |current_price - target| |best_cost - target|과 같은 경우
    - current_price
      - best_cost :=current_price
  - 0이 비트마스크에 없고 1이 비트마스크에 없으면
    - 루프에서 나오다
  - 범위 0에서 비트마스크 크기 - 1까지의 i에 대해
    - bitmask[i]가 2와 같지 않으면
      - 비트마스크[i] :=비트마스크[i] + 1
      - 루프에서 나오다
    - 그렇지 않으면
      - 비트마스크[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