สมมติว่าเรามีอาร์เรย์สองอาร์เรย์ชื่อ baseCosts มี n รายการที่เราสามารถเลือกฐานได้ และ toppingCosts มี m รายการที่เราสามารถเลือกท็อปปิ้งได้ และยังมีค่า target เราต้องปฏิบัติตามกติกาเหล่านี้เพื่อทำของหวาน:
- ต้องมีฐานพอดีหนึ่งชนิด
- สามารถเพิ่มท็อปปิ้งหนึ่งหรือมากกว่า หรือไม่มีท็อปปิ้งก็ได้
- แต่ละประเภทท็อปปิ้งมีได้สูงสุดสองชิ้น
baseCosts[i] แทนราคาของฐานไอศกรีมลำดับที่ i toppingCosts[i] แทนราคาของท็อปปิ้งลำดับที่ i ค่า target แทนราคาเป้าหมายของของหวาน เราต้องทำของหวานที่มีค่าใช้จ่ายรวมใกล้เคียง target มากที่สุด ต้องหาค่าใช้จ่ายที่ใกล้เคียง target มากที่สุด ถ้ามีคำตอบหลายค่า ให้ return ค่าที่ต่ำกว่า
เช่น ถ้าอินพุตคือ baseCosts = [2,8], toppingCosts = [4,5], target = 12 ผลลัพธ์จะเป็น 12 เพราะเราสามารถเลือกฐานราคา 8 แล้วท็อปปิ้งชนิดแรก 1 ชิ้นราคา 4 รวม 12
วิธีแก้ปัญหา
- best_cost := baseCosts[0]
- สำหรับ b ในช่วง 0 ถึงขนาดของ baseCosts - 1:
- bitmask := อาร์เรย์ขนาดเท่ากับ toppingCosts เติม 0
- ทำซ้ำอย่างไม่รู้จบ:
- current_price := baseCosts[b]
- สำหรับ j ในช่วง 0 ถึงขนาดของ bitmask - 1: current_price := current_price + bitmask[j] * toppingCosts[j]
- ถ้า current_price - target เท่ากับ 0: return 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 ไม่อยู่ใน bitmask และ 1 ไม่อยู่ใน bitmask: ออกจากลูป
- สำหรับ i ในช่วง 0 ถึงขนาดของ bitmask - 1:
- ถ้า bitmask[i] ไม่เท่ากับ 2: bitmask[i] := bitmask[i] + 1, ออกจากลูป
- มิฉะนั้น: bitmask[i] := 0
- return 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
เอาต์พุต
12
