Минимизация разницу между суммами

Question

Допустим, у вас есть список из 8 цен - например:

1$ 
2$ 
3$ 
4$ 
5$ 
6$ 
7$ 
8$ 

Вы хотите разделить цены на 2 группы по 4 цены каждого.

Пусть общая стоимость группы будет равна сумме индивидуальных цен группы. Как вы разделите группу таким образом, чтобы разница между двумя общими ценами была как можно меньше?

Очевидное решение состоит в том, чтобы попробовать все пары и посмотреть, какая из них самая низкая, но существует ли более эффективное решение, которое могло бы работать, если бы оно было расширено до более чем 8 цен или более двух групп?

Answer 1

Выглядит действительно невинно, но это сложная проблема.

Очевидное решение попробовать все пары и посмотреть, что является самым низким , но есть более эффективное решение, которое может работать, если это были распространены на более чем 8 цен или более 2-х групп?

Пока P != NP: Нет, обычно нет эффективного (полиномиального) решения. И очевидное решение (грубая сила AKA) имеет экспоненциальную сложность.

Пусть N = количество цен и K = количество подмножеств.

Partition problem for K=2 уже NP-полный. Итак, обобщенная версия также NP-полная. Если бы был найден эффективный (полиномиальный) алгоритм, это означало бы, что P = NP.

Вы можете попробовать субоптимальные решения, они будут намного быстрее, но без гарантии оптимального решения. Для K = 2 Wikipedia описывает pseudo-polynomial time dynamic programming algorithm. При K> 2:

Проблема 3-перегородка сильно отличается от задачи Partition и не имеет псевдо-полиномиального алгоритма времени, если P = NP. Для обобщения проблемы раздела, см. Bin packing problem.