Với thang máy có trọng lượng tối đa và n người có trọng lượng x_i, hãy tìm số lượng chuyến đi tối thiểu cần thiết

Question

input: 
max_weight = 550 
n = 4 
x_i = [120, 175, 250, 150] 

output: 
2 
// [[250, 175, 120], [150]] 

Ấn tượng ban đầu của tôi là trông rất giống với vấn đề thay đổi đồng xu/lập trình động, tuy nhiên nó không phải là đồng xu thay đổi (mà sẽ yêu cầu số lượng trọng lượng nhỏ nhất để tạo ra số tiền chính xác), và nó không phải là ba lô (trọng số không có giá trị và nó giống như tôi có thể có nhiều hơn 1 chiếc ba lô).

Có một tên/giải pháp chung cho vấn đề này không?

Answer 1

Đây thực sự là một (1D) Bin Packing problem:

Trong vấn đề bin đóng gói, vật khối lượng khác nhau phải được đóng gói vào một số hữu hạn các thùng hoặc container mỗi khối lượng V một cách rằng giảm thiểu số lượng thùng được sử dụng. Trong lý thuyết phức tạp tính toán, nó là một vấn đề NP-hard tổ hợp.

Ở đây những người lập bản đồ trên các đối tượng trên thùng trên các chuyến đi. Giống như vấn đề đóng gói thùng rác, chúng tôi muốn giảm thiểu số lần cưỡi "được sử dụng" và mỗi người chiếm một "khối lượng" nhất định (trọng lượng của người đó).

Sự cố đóng gói thùng rác - như đã nói trong bài viết - NP-hard. Chúng ta có thể sử dụng lập trình động (nhưng nó vẫn có - trường hợp xấu nhất - thời gian mũ).

Giấy A New Algorithm for Optimal Bin Packing bởi Richard E. Korf thảo luận một thuật toán để giải quyết vấn đề này chính xác. Nó hoạt động bằng cách sử dụng phương pháp heuristic đầu tiên và tính toán giới hạn dưới, sau đó sử dụng nhánh và liên kết để lặp đi lặp lại lấy được một giải pháp tốt hơn so với phương pháp heuristic cho đến khi đạt tới giới hạn dưới, hoặc không tìm thấy giải pháp nào nữa.

Answer 2

Hãy sửa tôi nếu tôi sai (không hiệu quả nhất), nhưng tôi nghĩ bạn có thể đặt tất cả các trọng số vào max heap và sau đó sử dụng greedy algorithm để chọn các bộ.

Answer 3

Bạn đang đi đúng hướng. Vấn đề được giải quyết bằng thuật toán thay đổi tiền xu thay đổi: thay vì yêu cầu một giải pháp chính xác, bạn sẽ tìm thấy giải pháp đạt được tổng số cao nhất mà không vượt quá số tiền mục tiêu. Tất nhiên, nếu bạn tìm thấy một giải pháp mà thiếu hụt là ít hơn bất kỳ yếu tố thiết lập còn lại, bạn dừng lại và báo cáo giải pháp đó.

Khi bạn tìm thấy giải pháp, hãy xóa trọng số "đã sử dụng" và lặp lại cho đến khi bạn đã phân bổ tất cả. Số lần lặp lại là số lượng thang máy bạn cần.

Nếu bạn sắp xếp các phần tử theo thứ tự giảm dần, điều này sẽ mang lại cho bạn sự bắt đầu "tham lam" với tính năng quay lại. Tôi nghi ngờ rằng điều này là hợp lý gần với tối ưu cho nhiều trường hợp, đặc biệt là nếu bạn ghi nhớ các kết quả để bạn không lặp lại những sai lầm trong lần lặp tiếp theo.

Bạn có thể thử một số trường hợp bệnh lý, chẳng hạn như một giới hạn là 100, và trọng lượng cực đoan như

[93, 91, ..., 5, 4, 4] 

Các "tham lam" thuật toán đi cho 93 + 5 đầu tiên, nhưng sau đó giải quyết cho 91 + 4 + 4 (giải pháp gần hơn). Đây là nơi memoization có ích.

Điều đó có dẫn bạn đến một giải pháp không?