โปรแกรมหา Units สูงสุดที่บรรทุกบนรถบรรทุกได้ (Python)

โจทย์

มีกล่องหลายประเภท boxTypes[i] = [จำนวนกล่อง, unitsต่อกล่อง] รถบรรทุกบรรทุกได้สูงสุด k กล่อง เลือกกล่องเพื่อให้ Units รวมมากที่สุด

ตัวอย่าง: boxTypes = [[2,4],[3,3],[4,2]], k = 6 → เลือกประเภท 1 (2 กล่อง×4), ประเภท 2 (3 กล่อง×3), ประเภท 3 (1 กล่อง×2) = 8+9+2 = 19

อัลกอริธึม (Greedy)

1. เรียง boxTypes ตาม Units ต่อกล่อง มากไปน้อย
2. หยิบกล่องตามลำดับจนครบ k กล่อง

โค้ด Python

def solve(boxTypes, k):
    boxTypes.sort(key=lambda x: x[1], reverse=True)
    total = 0
    fill = 0
    for i in boxTypes:
        if fill + i[0] <= k:
            fill += i[0]
            total += i[0] * i[1]
        else:
            total += (k - fill) * i[1]
            break
    return total

boxTypes = [[2,4],[3,3],[4,2]]
k = 6
print(solve(boxTypes, k))  # Output: 19

Input / Output

Input:  [[2,4],[3,3],[4,2]], 6
Output: 19