What is an algorithm for dividing a group of elements into 3 separate groups?

Question

I have this problem in my tutorial: Given a group of n elements, each of which has a different V (i) value, what is the best way to divide the elements into 3 groups so that the group with the highest value is minimal? Give meaning to this largest group.

I know how to make an option with two piles of this problem: for this, you just need to run the knapsack algorithm. However, I am rather puzzled by how to solve this problem. Can anyone give me any directions?

Answer: Pretty much the same as a 0-1 backpack, although 2D

Answer 1

A tough problem with homework. This is, in fact, an optimization version of the problem with 3 sections.

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

It is closely related to the packaging, section, and subset of the bin (and, as you noted, a backpack). However, this turns out to be strongly NP-Complete, which makes it harder than its cousins. In any case, I suggest you start by studying dynamic software solutions for the problems associated with them (I would start with a section, but find a non-Wikipedia explanation for the DP solution).

Update: I apologize. I misled you. A task with three sections splits the input into groups of 3, not 3 sets. The rest of what I said is still applicable, but with the new hope that your option is not completely np-complete.

Answer 2

I don’t know about the “Best” mathematically, but one obvious approach would be to create a population of groups initially with one element in each group. Then, while you have more groups than the required number of leaf groups, extract the two groups with the smallest values ​​and merge them into a new group, which you will add back to the collection. This is similar to how Huffman compression trees are built.

Example:

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

Answer 3

Let f [i] [j] [k] denote whether it is possible to have a value j in the first set and a value k in the second set, with the first elements i .

So, we have f[i][j][k] = f[i-1][jv[i]][k] or f[i-1][j][kv[i]] .

and initially we have f[0][0][0] = True .

for each f[i][j][k] = True , updating your answer depends on how you determine fairly .