Поиск решения или эвристического приближения для комбинаторной ситуации с тремя разделами

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

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

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

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


person GrabsAtStrawberries    schedule 29.11.2011    source источник
comment
Интересный вопрос. Мне кажется, что это усложнение проблемы с рюкзаком.   -  person Mr.Wizard    schedule 30.11.2011
comment
Кроме того, вы можете задать этот вопрос на math.stackexchange.com.   -  person Mr.Wizard    schedule 30.11.2011
comment
Являются ли цифры 48 и 3 адекватными для вашего фактического использования? С наследниками элементов ›› эта проблема выглядит проще.   -  person Mr.Wizard    schedule 30.11.2011
comment
Да, это связано с проблемой рюкзака. Да, это сложнее, по крайней мере, в теории. Я хотел бы алгоритм, даже если бы он работал на моем ПК 5 дней. Да, 48 и 3 — это реальные цифры: 48 украшений и 3 человека, которым нужно угодить.   -  person GrabsAtStrawberries    schedule 01.12.2011
comment
В этом случае может сработать чрезвычайно простой алгоритм. Можете ли вы предоставить некоторые образцы наборов данных?   -  person Mr.Wizard    schedule 01.12.2011
comment
Я думаю, что это похоже на решение: jstor.org/pss/2631900, но не уверен, что требования к доступу относятся к остальной части. Тоже выглядит довольно сложно.   -  person Helen    schedule 05.12.2011


Ответы (1)


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

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

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

person Community    schedule 08.12.2011