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

Giả sử chúng ta có một tập hợp các hộp được biểu diễn dưới dạng mảng 2D được gọi là boxTypes, trong đó boxTypes [i] chứa hai phần tử [số hộp loại i, số đơn vị trên mỗi hộp loại i]. Bây giờ chúng ta còn có một giá trị khác là k, là số hộp tối đa có thể xếp được trên xe tải đó. Chúng ta có thể chọn bất kỳ hộp nào để xếp lên xe tải miễn là số lượng hộp không vượt quá k. Chúng ta phải tìm tổng số đơn vị tối đa có thể xếp lên xe tải.

Vì vậy, nếu đầu vào là boxTypes =[[2,4], [3,3], [4,2]], k =6, thì đầu ra sẽ là 19, vì có

• 2 hộp loại 1 và mỗi hộp chứa 4 chiếc

• 3 hộp loại 2 và mỗi hộp chứa 3 chiếc

• 4 hộp loại 3 và mỗi hộp chứa 2 chiếc

như k =6, chúng ta có thể lấy tất cả các hộp loại 1 và 2, và chỉ một hộp loại 3, do đó sẽ có (2 * 4) + (3 * 3) + 2 =8 + 9 +2 =19 mục .

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• sắp xếp hộp Các loại dựa trên số lượng các mục có trong mỗi hộp

• tổng:=0, điền:=0

• đối với mỗi i trong boxTypes, thực hiện

  • nếu điền + i [0] <=k thì

    • điền:=fill + i [0]

    • tổng:=tổng + i [0] * i [1]

  • nếu không,

    • tổng:=tổng + (k - điền) * i [1]

    • đi ra từ vòng lặp

• tổng trả lại

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

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

Đầu ra

19