Làm cách nào để chia danh sách các mục thành các phân vùng bằng nhau theo trọng lượng của sản phẩm?

Question

Tôi có một danh sách các mục đó là một chút như thế này:

[ 
    ["orange", 9], 
    ["watermelon", 3], 
    ["grapefruit", 6], 
    ["peach", 8], 
    ["durian", 2], 
    ["apricot", 6] 
] 

Tôi muốn chia danh sách này vào ... nói hai nhóm sao cho tổng các trọng lượng của các mục trong mỗi nhóm như bằng nhau, ví dụ:

List 1: 
    orange: 9 
    durian: 2 
    apricot: 6 
    TOTAL: 17 

List 2: 
    watermelon: 3 
    grapefruit: 6 
    peach: 8 
    TOTAL: 17 

Hiện tại tôi đang giải quyết điều này bằng cách duyệt qua danh sách theo thứ tự theo cách zigzag'esque. Chỉ định các vật phẩm có trọng lượng lớn hơn trong lần chuyền đầu tiên cho mỗi nhóm, đảm bảo các vật phẩm có trọng lượng ít hơn trên lần vượt thứ hai, v.v.

Điều này hoạt động tốt, nhưng nó có sai sót. Tôi nghĩ rằng một lần thứ hai thông qua các nhóm mà tôi trao đổi các mục giữa chúng sẽ dẫn đến các nhóm được phân phối đồng đều hơn, nhưng mã liên quan có thể trở nên quá phức tạp.

Có ai đó biết cách hiệu quả hơn hoặc thông minh hơn để thực hiện việc này không?

Cảm ơn!

Answer 1

Đây là phiên bản tối ưu hóa của partition problem, đó là NP-hoàn chỉnh, mặc dù, theo bài viết đó, "có những chẩn đoán giải quyết vấn đề trong nhiều trường hợp, hoặc là tối ưu hoặc xấp xỉ".

Phần methods của bài viết đó chứa một số cách để thực hiện các giải pháp gần đúng hoặc giả đa thức. Cụ thể, nếu bạn có thể sống với câu trả lời gần đúng, bạn có thể thử cách tiếp cận tham lam:

Một cách tiếp cận cho vấn đề, bắt chước cách trẻ chọn nhóm cho trò chơi là thuật toán tham lam, đi qua các con số theo thứ tự giảm dần, chỉ định từng thứ tự cho bất kỳ tập hợp con nào có tổng nhỏ hơn.

Thời gian chạy của phương pháp này là O(n^2) và được đảm bảo đưa bạn đến hệ số 4/3 của giải pháp chính xác.

Nếu bạn phải có giải pháp chính xác và tập dữ liệu của bạn đủ nhỏ, bạn luôn có thể sử dụng phương pháp bạo lực để tạo mọi khả năng (đây là số mũ, O(2^n)). Tùy thuộc vào nhu cầu hiệu suất của bạn, điều này có thể là đủ.

Answer 2

Bạn có thể tính tổng trọng số, chia cho số nhóm, đưa ra trọng số mục tiêu và sau đó lặp lại các mục theo thứ tự giảm dần để đưa chúng vào cùng một nhóm nếu chúng phù hợp hoặc dưới trọng số mục tiêu và vào nhóm khác nếu không.

Có lẽ một số nhà toán học ở đó có thể đưa ra bằng chứng chính thức về cách tốt nhất để làm điều đó, nhưng đó là suy nghĩ của tôi trên đỉnh đầu của tôi.

Answer 3

Nó sẽ không hoạt động. Ví dụ: S = {5, 5, 4, 3, 3}.