Как разбить список на два подсписка с почти равными средствами?

Question

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

Я понимаю, что это можно сделать, взяв все возможные комбинации и выбрав ту, которая дает наименьшее среднее отклонение, но существуют ли более эффективные способы сделать это? Возможно, не дает идеальной пары, но близко к ней.

Answer 1

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

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