Chương trình tìm số đơn vị tối đa có thể tải lên xe tải trong Python

Giả sử ta có tập hợp hộp biểu diễn bằng mảng 2D boxTypes, với boxTypes[i] = [số hộp loại i, số đơn vị/hộp loại i]. Có giá trị k là số hộp tối đa xe tải chở được. Ta có thể chọn hộp bất kỳ miễn số hộp không vượt quá k. Tìm tổng đơn vị tối đa có thể tải lên xe.

Ví dụ: boxTypes = [[2,4],[3,3],[4,2]], k = 6, kết quả là 19. Lấy hết 2 hộp loại 1 (4 đơn vị), 3 hộp loại 2 (3 đơn vị), 1 hộp loại 3 (2 đơn vị) = 8+9+2=19.

Giải thuật

1. Sắp xếp boxTypes theo số đơn vị/hộp giảm dần
2. total := 0, fill := 0
3. Với mỗi i trong boxTypes:
   • Nếu fill + i[0] <= k: fill += i[0], total += i[0] * i[1]
   • Ngược lại: total += (k - fill) * i[1], break
4. Trả về total

Ví dụ (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))

Input

[[2,4],[3,3],[4,2]], 6

Output

19