Chương trình tìm chi phí tráng miệng gần nhất mục tiêu trong Python

Cho mảng baseCosts (n món cơ sở), toppingCosts (m topping), và target. Quy tắc làm tráng miệng:

• Chọn đúng 1 base
• Có thể thêm 0, 1, hoặc 2 mỗi loại topping

Tìm chi phí gần target nhất. Nếu nhiều đáp án, chọn cái nhỏ hơn.

Ví dụ: baseCosts = [2,8], toppingCosts = [4,5], target = 12, đầu ra = 12 (base 8 + 1 topping 4).

Giải pháp

Duyệt tất cả tổ hợp topping (3^m cách) cho mỗi base:

• best_cost := baseCosts[0]
• Với mỗi base b:
  • bitmask := mảng kích thước toppingCosts điền 0
  • Lặp vô hạn:
    • current_price := baseCosts[b] + sum(bitmask[j] * toppingCosts[j])
    • Cập nhật best_cost nếu gần target hơn
    • Nếu bitmask toàn 2: break
    • Tăng bitmask như đếm cơ số 3
• Trả về best_cost

Ví dụ minh họa

Xem triển khai sau để hiểu rõ hơn:

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))

Đầu vào

[2,8], [4,5], 12

Đầu ra

12