What is an algorithm to split a group of items into 3 separate groups fairly?

Question

I have this problem in my textbook: Given a group of n items, each with a distinct value V(i), what is the best way to divide the items into 3 groups so the group with the highest value is minimIzed? Give the value of this largest group.

I know how to do the 2 pile variant of this problem: it just requires running the knapsack algorithm backwards on the problem. However, I am pretty puzzled as how to solve this problem. Could anyone give me any pointers?

Answer: Pretty much the same thing as the 0-1 knapsack, although 2D

Answer 1

Tough homework problem. This is essentially the optimization version of the 3-partition problem.

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

It is closely related to bin packing, partition, and subset-sum (and, as you noted, knapsack). However, it happens to be strongly NP-Complete, which makes it a harder than its cousins. Anyway, I suggest you start by looking at dynamic programming solutions to the related problems (I'd start with partition, but find a non-wikipedia explanation of the DP solution).

Update: I apologize. I have mislead you. The 3-partition problem splits the input into sets of 3, not 3 sets. The rest of what I said still applies, but with the renewed hope that your variant isn't strongly np-complete.