Chương trình tìm chi phí món tráng miệng gần nhất bằng Python

Giả sử chúng ta có hai mảng được gọi là baseCosts với n mục từ chúng, chúng ta có thể chọn base và toppingCosts với m mục từ chúng, chúng ta có thể chọn lớp trên và cũng có một giá trị đích. Chúng ta phải tuân theo những quy tắc này để làm món tráng miệng.

Phải có chính xác một cơ sở.
Chúng tôi có thể thêm một hoặc nhiều lớp phủ hoặc không có lớp phủ nào cả.
Có nhiều nhất hai trong số mỗi loại lớp phủ.

Ở đây baseCosts [i] đại diện cho giá của kem nền thứ i. Giá của phần trên cùng [i] đại diện cho giá của một trong những phần trên cùng thứ i. Giá trị mục tiêu đại diện cho giá mục tiêu cho món tráng miệng. Chúng ta phải làm một món tráng miệng với tổng chi phí càng gần với mục tiêu càng tốt. Chúng tôi phải tìm ra chi phí gần nhất có thể của món tráng miệng để nhắm mục tiêu. Nếu có nhiều câu trả lời, hãy trả lại câu trả lời thấp hơn.

Vì vậy, nếu đầu vào giống như baseCosts =[2,8], toppingCosts =[4,5], target =12, thì đầu ra sẽ là 12 vì chúng ta có thể lấy cơ sở với chi phí 8, sau đó lấy 1 trong số cao nhất đầu tiên với chi phí 4 và không có lớp trên cùng loại 2, vì vậy tổng chi phí 8 + 4 =12.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

best_cost:=baseCosts [0]
đối với b trong phạm vi 0 đến kích thước của baseCosts - 1, thực hiện
- bitmask:=một mảng có kích thước bằng với kích thước của toppingCosts và điền bằng 0
- làm những điều sau vô hạn, hãy làm
  - current_price:=baseCosts [b]
  - đối với j trong phạm vi 0 đến kích thước của mặt nạ bit - 1, thực hiện
    - current_price:=current_price + bitmask [j] * toppingCosts [j]
  - nếu giá_trả_nghiệp hiện_trên - mục tiêu giống 0, thì
    - mục tiêu trả lại
  - ngược lại khi | giá_trị_ngày - mục tiêu | <| best_cost - target |, sau đó
    - best_cost:=current_price
  - ngược lại khi | giá_trị_ngày - mục tiêu | giống với | best_cost - target |, sau đó là
    - nếu current_price
      - best_cost:=current_price
  - nếu 0 không có trong bitmask và 1 không có trong bitmask, thì
    - đi ra từ vòng lặp
  - đối với tôi trong phạm vi từ 0 đến kích thước của mặt nạ bit - 1, thực hiện
    - nếu bitmask [i] không giống như 2, thì
      - bitmask [i]:=bitmask [i] + 1
      - đi ra từ vòng lặp
    - nếu không,
      - mặt nạ bit [i]:=0
trả lại best_cost

Ví dụ

Hãy cùng chúng tôi xem cách 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

Chương trình tìm chi phí món tráng miệng gần nhất bằng Python

Ví dụ

Đầu vào

Đầu ra