Chương trình Python tìm chi phí tối thiểu điền trái cây tối ưu

Cho danh sách fruits mỗi phần tử [cost, size, total]. Có k giỏ容量 cap. Ràng buộc:

1. Mỗi giỏ chỉ chứa 1 loại trái cây.
2. Mỗi giỏ đầy nhất có thể.
3. Chi phí rẻ nhất có thể.

Tìm chi phí tối thiểu để điền nhiều giỏ nhất.

Ví dụ

fruits = [[5,2,3], [6,3,2], [2,3,2]], k=2, cap=4
Output: 12
Giải thích: Giỏ 1: 2 trái loại 0 (size 2+2=4, cost 10). Giỏ 2: 1 trái loại 2 (size 3, cost 2). Tổng=12.

Thuật toán

1. Với mỗi loại trái cây, tính các "option" giỏ có thể tạo: số trái/giỏ (fnum), chi phí/giỏ (bcost), số giỏ khả thi (bnum), không gian thừa (left_cap).
2. Sắp xếp options theo left_cap tăng dần (ưu tiên giỏ đầy hơn), sau đó bcost tăng (ưu tiên rẻ hơn).
3. Chọn lần lượt cho đến khi hết k giỏ.

Code Python

def solve(fruits, k, cap):
    options = []
    for c, s, t in fruits:
        while t > 0:
            fnum = min(cap // s, t)  # số trái/giỏ tối đa
            if fnum == 0: break
            bnum = t // fnum         # số giỏ tạo được
            options.append((cap - fnum * s, fnum * c, bnum))  # (left_cap, bcost, 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

# Test
fruits = [[5,2,3],[6,3,2],[2,3,2]]
k, cap = 2, 4
print(solve(fruits, k, cap))  # 12

Giải thích options

Fruit 0: c=5,s=2,t=3
  fnum=min(4//2,3)=2, bnum=3//2=1 -> option: (left=0, cost=10, bnum=1), t=1
  fnum=min(4//2,1)=1, bnum=1//1=1 -> option: (left=2, cost=5,  bnum=1), t=0

Fruit 1: c=6,s=3,t=2
  fnum=min(4//3,2)=1, bnum=2//1=2 -> option: (left=1, cost=6, bnum=2), t=0

Fruit 2: c=2,s=3,t=2
  fnum=min(4//3,2)=1, bnum=2//1=2 -> option: (left=1, cost=2, bnum=2), t=0

Options sorted by (left_cap, bcost):
(0,10,1), (1,2,2), (1,6,2), (2,5,1)

Chọn: (0,10,1) -> ans=10, k=1
      (1,2,2)  -> ans=12, k=0 -> stop

Độ phức tạp

• Thời gian: O(F log F) (F = tổng options, sort).
• Không gian: O(F).