สมมติว่าเรามีรายการที่เรียกว่า fruits และอีกสองค่า k และ cap โดยที่ผลไม้แต่ละชนิด[i] มีค่าสามค่า:[c, s, t] ค่านี้บ่งชี้ว่าผลไม้ i มีราคาค่า c แต่ละค่า ขนาดของแต่ละค่าคือ s และมีทั้งหมด t ค่า k คือจำนวนกระเช้าผลไม้ที่มีความจุสูงสุด เราต้องการกรอกตะกร้าผลไม้ด้วยข้อจำกัดดังต่อไปนี้ -
- ตะกร้าแต่ละใบสามารถใส่ผลไม้ชนิดเดียวกันได้เท่านั้น
- ตะกร้าแต่ละใบควรเต็มให้มากที่สุด
- ตะกร้าแต่ละใบควรจะถูกที่สุด
เราจึงต้องหาต้นทุนขั้นต่ำในการเติมตะกร้าให้ได้มากที่สุด
ดังนั้น หากอินพุตเป็นเหมือนผลไม้ =[[5, 2, 3],[6, 3, 2],[2, 3, 2]] k =2 cap =4 ดังนั้นผลลัพธ์จะเป็น 12 เพราะเรา ได้ 0 ผลไม้สองผล เพราะด้วยสองสิ่งนี้ เราสามารถทำให้ตะกร้าแรกเต็มได้ขนาดรวม 2+2=4 ในราคา 5+5=10 จากนั้นเราใช้ผลไม้ 2 อย่างเพราะราคาถูกกว่า ราคานี้ 2 หน่วย
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ตัวเลือก :=รายการใหม่
- สำหรับแฝดสามแต่ละตัว (c, s, t) ในผลไม้ ทำ
- ในขณะที่ t> 0, ทำ
- fnum :=ขั้นต่ำของพื้น (cap / s) และ t
- ถ้า fnum เหมือนกับ 0 แล้ว
- ออกมาจากลูป
- bnum :=ชั้นของ t / fnum
- ใส่ triplet (cap - fnum * s, fnum * c, bnum) ต่อท้ายตัวเลือก
- t :=t - bnum * fnum
- ในขณะที่ t> 0, ทำ
- ตอบ :=0
- สำหรับแฝดแฝดแต่ละตัว (left_cap, bcos, bnum) ในรายการตัวเลือกที่เรียงลำดับแล้ว ทำ
- bfill :=ขั้นต่ำของ k และ bnum
- ans :=ans + bcost * bfill
- k :=k - bfill
- ถ้า k เท่ากับ 0 แล้ว
- ออกมาจากลูป
- คืนสินค้า
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def solve(fruits, k, cap): options = [] for c, s, t in fruits: while t > 0: fnum = min(cap // s, t) if fnum == 0: break bnum = t // fnum options.append((cap - fnum * s, fnum * c, bnum)) t -= bnum * fnum ans = 0 for left_cap, bcost, bnum in sorted(options): bfill = min(k, bnum) ans += bcost * bfill k -= bfill if k == 0: break return ans fruits = [[5, 2, 3],[6, 3, 2],[2, 3, 2]] k = 2 cap = 4 print(solve(fruits, k, cap))
อินพุต
[[5, 2, 3],[6, 3, 2],[2, 3, 2]], 2, 4
ผลลัพธ์
12
