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

Question

У меня есть набор из 18 значений (это всегда будет 18), которые мне нужно распределить на два набора, один из 10 предметов и один из 8 предметов.

Правило для распределения состоит в том, что значения каждого набора должны быть равны (или максимально приближены) к определенному известному значению - поэтому в первом наборе сумма значений должна быть как можно ближе к1500000, а во втором наборе сумма значений должна быть как можно ближе к 1000000.

Каков наилучший (и это может означать самый простой) алгоритм для этого?

Дальнейшее пояснение, все значения находятся в диапазоне от 110000 до 200000. Значения всегда кратны 100 и являются целыми положительными числами, и могут быть дубликаты.

Answer 1

Есть только 43758 таких выборов.Пройдите через каждого из них и найдите лучшее.

Answer 2

Это проблема оптимизации.Здесь у вас есть два критерия оптимизации, которые следует объединить в один.Например, как это:

F(A, B) = w1*abs(sum(A) - 1500000) + w2*abs(sum(B) - 1000000)

, где A и B - ваши множества, sum () - сумма элементов в наборе, а w1 и w2 - веса.1007 * Тогда вы должны найти стратегию для итерации возможных комбинаций.Самая простая стратегия - найти все 10 комбинаций из 18 и выбрать ту, которая минимизирует F (A, B).Есть C (18,10) = 43758 комбинаций.

Answer 3

Хотя метод грубой силы, вероятно, лучше всего подходит для решения этой проблемы, есть и другие приемы, которые вы можете использовать, если хотите получить приблизительное решение или метод грубой силы все еще слишком дорог.основная идея состоит в том, чтобы привязать значения к небольшой сетке, и , а затем сделать грубую силу для (намного меньшего) набора записей в сетке.

в вашем случае (делая вид, что Iуже разделены на 100), все числа между 1100 и 2000, так что вы можете «привязать» их к 10 целым числам 1100, 1200 и так далее.Максимальная ошибка при выполнении - не более 50/1100, что составляет менее 5%.Теперь вы вдвое сократили размер ввода, что заставляет грубую силу работать немного быстрее.

Опять же, я бы не рекомендовал это, если (а) грубая сила сейчас действительно медленная или (а) размер проблемы не превышает 18.

ps проблема называется SUBSET SUM (или иногда KNAPSACK в зависимости от состава) и является NP-полным. Вот ссылка на идею аппроксимации.

Answer 4

Ваша проблема, как указано, np, если нет данных для шаблона.

Единственный способ добиться наилучшего ответа - найти все перестановки от 18 до 10 и 8 и соответствующие суммы.Вес в соответствии с вашими предпочтениями.

Answer 5

Похоже, проблема оптимизации для меня. Случайно разделите значения на два набора, а затем начните менять значения (используйте хорошую эвристику) и примите изменение, если результат будет лучше.