Seeking a solution algorithm to the 3-partition problem I need to divide 48 pieces of jewelry between 3 inheritors so as to give equal, or nearly equal value, to each. I have learned that this is called the 3-partition problem. I solved it for 9 pieces of jewely by exhaustive enumeration (some 19,000 possibilities) in a spreadsheet (LibreOffice Calc). No big deal. But all 48 pieces becomes a big deal.
I don't actually need a perfect solution. A heuristic algorithm would suffice if it were acknowledged as an acceptable solution scheme by some set of professionals; programmers, estate settling lawyers, etc. In other words using a technique recognized as "good enough" will be good enough for my purpose.
This question is also posted on StackOverflow. They suggested I post here.
Thank you,
David
 A: There exists a pseudo-polynomial time dynamic programming solution to this problem, for which running time and storage complexity depend on the sum of costs of the pieces of jewelry, denoted $S$. If the sum of costs, $S$, is small then the algorithm would be practical as its storage is $O(S^2)$ and its running time is $O(S^2N)$, $N$ being the number of pieces (48 here).
To get a sense of the algorithm take a look at the Subset sum problem Wikipedia page--dynamic programming solution. This concerns finding a subset of items which sums to a particular cost. Clearly you can solve the 2-partition problem by using the subset sum solutions, i.e., by enumerating over all the potential subset sums, and choosing the one that you prefer for any reason.
Now generalizing to 3-partition is straightforward. You basically solve the double-subset sum problem. You store $Q(i,s, t)$ to be the value (true or false) of "whether there are two disjoint subsets of $x_1, \ldots, x_i$ which respectively sum to $s$ and $t$". You can easily update $Q(i, s, t)$ by adding new items. Again one can enumerate over the potential $Q(N, s, t)$'s and choose the one that is considered best.
Obviously even if $S$ is large, the costs can be quantized using larger cost units, which results in a measurable upper bound on the error. This also can be used combined with the solution of Brendan McKay to guide a local search algorithm.
A: To get a good approximation, I suggest a local refinement algorithm. Define some success measure (like the maximum value of a share minus the minimum value).
Start with any distribution into three shares.
Now move a small number of pieces into different shares if they improve the
success measure.  Keep doing that until no such improvement is possible.  With 48 items, you should be able to find a partition where no movement of 4 or fewer items improves the success measure, and this will be a fairly good solution.
Start with different random partitions to see if you get the same final result. If so, there is a fair chance (in practice, not in theory!) that you have the best solution. If you get multiple final results, you can at least choose the best one.
A variation is to allow movement of a small number of pieces with low probability even if the success gets worse. Maybe the probability can depend on how much worse the success gets.  This can get you out of local minima but you will never find the global minimum if you set the probabilities too high.
More sophisticated algorithms like simulated annealing, genetic search, and tabu search are out there and can be adapted to this problem.
