โปรแกรมหาต้นทุนขั้นต่ำในการใส่ผลไม้ลงตะกร้าอย่างเหมาะสมใน Python

คำอธิบายปัญหา

กำหนดลิสต์ fruits โดยแต่ละรายการเป็น [c, s, t] = [ราคาต่อหน่วย, ขนาดต่อหน่วย, จำนวนทั้งหมด] มีตะกร้า k ใบ แต่ละใบจุได้ cap หน่วย ข้อจำกัด:

1. ตะกร้าใบใดจุได้แค่ชนิดเดียว
2. ตะกร้าแต่ละใบต้องเต็มที่สุดเท่าที่จะเป็นไปได้
3. เลือกชนิดที่ถูกที่สุด

หาต้นทุนรวมน้อยที่สุดเพื่อเติมตะกร้าให้มากที่สุด

ตัวอย่าง

fruits = [[5,2,3],[6,3,2],[2,3,2]], k=2, cap=4 → Output: 12

• ผลไม้ชนิด 0: ขนาด 2, ราคา 5 → ใส่ 2 ผล/ตะกร้า (เต็ม 4) ต้อง 1 ตะกร้า ราคา 10
• ผลไม้ชนิด 2: ขนาด 3, ราคา 2 → ใส่ 1 ผล/ตะกร้า (เหลือที่ 1) ราคา 2
• รวม = 12

ขั้นตอนการแก้ปัญหา

1. สร้างรายการตัวเลือก options จากแต่ละชนิดผลไม้:
   • คำนวณ fnum = min(cap // s, t) = จำนวนผลสูงสุดต่อตะกร้า
   • bnum = t // fnum = จำนวนตะกร้าที่ทำได้
   • เก็บ (cap - fnum*s, fnum*c, bnum) = (พื้นที่เหลือ, ราคาต่อตะกร้า, จำนวนตะกร้า)
2. เรียง options (Python เรียงตาม tuple: พื้นที่เหลือน้อยก่อน → เต็มกว่า, ราคาถูกกว่า)
3. เลือกตะกร้าจากตัวเลือกที่ดีที่สุดจนครบ k ใบ

การตนการทำงาน (Python)

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))  # Output: 12

อินพุต / เอาต์พุต

Input:  [[5, 2, 3], [6, 3, 2], [2, 3, 2]], 2, 4
Output: 12