โปรแกรมหาค่าขนมที่ใกล้เคียงที่สุดใน Python

สมมติว่าเรามีสองอาร์เรย์ที่เรียกว่า baseCosts โดยมี n รายการจากพวกเขา เราสามารถเลือกฐานและค่า toppingCosts กับ m รายการจากพวกเขา เราสามารถเลือกท็อปปิ้งและยังมีค่าเป้าหมายอีกด้วย ต้องทำตามกฎเหล่านี้เพื่อทำขนม

• ต้องมีฐานเดียวกันเท่านั้น

• เราเติมท็อปปิ้งได้ตั้งแต่หนึ่งอย่างขึ้นไป หรือใส่ท็อปปิ้งไม่ได้เลยก็ได้

• มีท็อปปิ้งอย่างละ 2 ชนิด

ที่นี่ baseCosts[i] หมายถึงราคาของฐานไอศกรีม ith toppingCosts[i] หมายถึงราคาของหนึ่งใน ith topping มูลค่าเป้าหมายคือราคาเป้าหมายของขนม เราต้องทำขนมด้วยต้นทุนรวมใกล้เคียงกับเป้าหมายมากที่สุด เราต้องหาค่าขนมให้ใกล้เคียงกับเป้าหมายมากที่สุด หากมีหลายคำตอบ ให้ส่งคืนคำตอบที่ต่ำกว่า

ดังนั้นหากอินพุตเป็นเหมือน baseCosts =[2,8], toppingCosts =[4,5], target =12 ผลลัพธ์จะเป็น 12 เพราะเราสามารถใช้ฐานด้วยต้นทุน 8 แล้วจึงใช้ 1 ของการเติมครั้งแรกด้วยต้นทุน 4 และไม่มีท็อปปิ้งแบบที่ 2 ดังนั้นราคารวม 8+4 =12

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• best_cost :=baseCosts[0]

• สำหรับ b ในช่วง 0 ถึงขนาดของ baseCosts - 1 ทำ

  • bitmask :=อาร์เรย์ที่มีขนาดเท่ากับขนาดของ toppingCosts และเติมด้วย 0

  • ทำสิ่งต่อไปนี้อย่างไม่สิ้นสุด ทำ

    • current_price :=baseCosts[b]

    • สำหรับ j ในช่วง 0 ถึงขนาดของบิตมาสก์ - 1 ทำ

      • current_price :=ปัจจุบัน_price + bitmask[j] * toppingCosts[j]

    • ถ้า current_price - เป้าหมายเท่ากับ 0 แล้ว

      • คืนเป้าหมาย

    • มิฉะนั้น เมื่อ |current_price - target| <|best_cost - target| จากนั้น

      • best_cost :=current_price

    • มิฉะนั้น เมื่อ |current_price - target| เหมือนกับ |best_cost - target| จากนั้น

      • ถ้าราคาปัจจุบัน

        • best_cost :=current_price

    • ถ้า 0 ไม่ได้อยู่ในบิตมาสก์และ 1 ไม่ได้อยู่ในบิตมาสก์แล้ว

      • ออกจากวง

    • สำหรับฉันในช่วง 0 ถึงขนาดของบิตมาสก์ - 1 ทำ

      • ถ้า 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))

อินพุต

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

ผลลัพธ์

12