寻求三分区组合情况的解或启发式近似 [英] Seeking a solution or a heursitic approxmation for the 3-partition combinatorial situation

问题描述

我该如何向3个继承者中的每个继承者分发48个具有其自身美元价值的项目，以使分配给每个继承者的价值相等或几乎相等？

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?

这是一种形式的分区问题是NP完全的（或某些），因此不可能完美地回答48个项目。我正在寻找一种实用且公认的近似算法来实现这一目标。这是许多人在解决遗嘱和财产时面临的问题。答案必须在某处！答案可以是计算机脚本，也可以是手动方法。

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".

编程语言env：LibreOffice中的Visual Basic
其他研究：维基百科，MathIsFun，CodingTheWheel

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

推荐答案

我从justanswer.com找到了足够好的答案。足以使分割珠宝的合法性和足够接近使各方满意的程度。过程：

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:

按值的降序对项目进行排序。使用贪婪算法：从第一个项目（最有价值）开始，并填充下一个垃圾箱（有3个继承者，因此有3个垃圾箱），直到该垃圾箱不再是价值最小的垃圾箱。选择具有后续最小值的容器，并类似地填充它。重复。

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.

欢迎评论。

这篇关于寻求三分区组合情况的解或启发式近似的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！