Thuật toán chia một nhóm các mục thành 3 nhóm riêng biệt là gì?

Question

Tôi có vấn đề này trong sách giáo khoa của tôi: Cho một nhóm n mục, mỗi mục có giá trị riêng biệt V (i), cách tốt nhất để chia các mục thành 3 nhóm để nhóm có giá trị cao nhất là minimIzed? Cho giá trị của nhóm lớn nhất này.

Tôi biết cách thực hiện biến thể 2 cọc của vấn đề này: nó chỉ yêu cầu chạy thuật toán ba lô ngược về vấn đề này. Tuy nhiên, tôi khá bối rối khi làm thế nào để giải quyết vấn đề này. Bất cứ ai có thể cho tôi bất kỳ con trỏ?

Trả lời: Khá nhiều thứ giống như chiếc ba lô 0-1, mặc dù 2D

Answer 1

Vấn đề về bài tập về nhà khó khăn. Đây thực chất là phiên bản tối ưu của bài toán 3 phân vùng.

http://en.wikipedia.org/wiki/3-partition_problem

Nó liên quan chặt chẽ đến đóng gói bin, phân vùng, và tập hợp con-sum (và, như bạn đã nói, ba lô). Tuy nhiên, nó sẽ xảy ra với NP-Complete mạnh mẽ, khiến nó khó hơn người anh em họ của nó. Dù sao, tôi đề nghị bạn bắt đầu bằng cách nhìn vào các giải pháp lập trình động cho các vấn đề liên quan (tôi bắt đầu với phân vùng, nhưng tìm một giải thích không wikipedia của giải pháp DP).

Cập nhật: Tôi xin lỗi. Tôi đã đánh lừa bạn. Bài toán 3 phân vùng tách đầu vào thành bộ 3, không phải 3 bộ. Phần còn lại của những gì tôi nói vẫn áp dụng, nhưng với hy vọng mới mà biến thể của bạn không hoàn toàn np-hoàn thành.

Answer 2

Tôi không biết về "Tốt nhất" về mặt toán học, nhưng một cách tiếp cận rõ ràng là xây dựng dân số nhóm ban đầu với một mục trong mỗi nhóm. Sau đó, miễn là bạn có nhiều nhóm hơn số lượng nhóm cuối cùng mong muốn, hãy trích xuất hai nhóm với các giá trị thấp nhất và kết hợp chúng thành một nhóm mới mà bạn thêm lại vào bộ sưu tập. Điều này tương tự như cách Huffman nén cây được xây dựng.

Ví dụ:

1 3 7 9 10 
becomes 
4(1+3) 7 9 10 
becomes 
9 10 11(1+3+7) 

Answer 3

Hãy f [i] [j] [k] biểu thị cho dù đó có thể có giá trị j trong tập đầu tiên và giá trị k trong tập thứ hai, với số đầu tiên i mục.

Vì vậy, chúng tôi có f[i][j][k] = f[i-1][j-v[i]][k] or f[i-1][j][k-v[i]].

và ban đầu chúng tôi có f[0][0][0] = True.

cho mỗi f[i][j][k] = True, cập nhật câu trả lời của bạn tùy thuộc vào cách bạn xác định khá.