В поисках решения или эвристического приближения для комбинаторной ситуации с 3 разделами - PullRequest
2 голосов
/ 30 ноября 2011

Как мне распределить 48 элементов, каждый со своим собственным значением в долларах, каждому из 3 наследников, чтобы значение, данное каждому, было равным или почти равным?

Это форма проблемы разделения с NP-полный (или некоторые такие) и, следовательно, невозможно полностью ответить с 48 пунктов.Я ищу практичный и общепризнанный приблизительный алгоритм для этого.Это проблема, с которой сталкиваются многие при разрешении завещаний и сословий.Ответ должен быть где-то там!Ответом может быть компьютерный сценарий или просто ручной метод.

Эвристики, которая является "общепринятой", будет достаточно.С моей шляпой программиста я ищу почти идеальное решение.С моей шляпой по законническому исполнителю я ищу что-то, для чего есть общепринятый или юридический прецедент как «достаточно хороший».

Язык программирования env: visual basic в LibreOffice Другие исследования: Wikipedia, MathIsFun, CodingTheWheel

1 Ответ

0 голосов
/ 08 декабря 2011

Я нашел «достаточно хороший» ответ от justanswer.com. Достаточно хорош для законности деления драгоценностей и достаточно близко, чтобы быть равным, чтобы удовлетворить все стороны. Процедура:

Сортировка элементов в порядке убывания значения. Используйте жадный алгоритм: начните с 1-го элемента (самого ценного) и заполните следующий бин (есть 3 наследника, то есть 3 бина), пока этот бин больше не будет бином наименьшего значения. Выберите бин с последующим наименьшим значением и аналогичным образом заполните его. Повторите.

Комментарии приветствуются.

...