Seeking a solution or a heursitic approxmation for

问题:

How do I distribute 48 items each with its own dollar value to each of 3 inheritors so that the value given to each is equal or nearly equal?

This is a form of partitioning problem with is NP-complete (or some such) and therefore impossible to perfectly answer with 48 items. I'm looking for a practical and generally acknowledged approximate algorithm to do this. It's a problem faced by many in resolving wills and estates. Answer must be out there somewhere! The answer could be a computer script or just a manual method.

A heuristic that is "Generally Accepted" would suffice. With my programmer hat on I seek a near-perfect solution. With my legalistic executor hat on I seek something for which there is a generally accepted or legal precedent as being "good enough".

Programming Language env: visual basic in LibreOffice Other research: Wikipedia, MathIsFun, CodingTheWheel

回答1:

I have found a "good enough" answer from justanswer.com. Good enough for the legalities of dividing up the jewelry and close enough to being equal to satisfy all parties. The procedure:

Sort the items in descending order of value. Use greedy algorithm: start with 1st item (the most valuable) and fill the next bin (there are 3 inheritors so 3 bins) until that bin is no longer the bin of least value. Choose bin of subsequent least value and similarly fill it. Repeat.

Comments welcome.