Проблема суммы подмножеств, где каждое число можно сложить или вычесть - PullRequest
Новая
       20

Проблема суммы подмножеств, где каждое число можно сложить или вычесть

0 голосов
/ 21 апреля 2011

Учитывая набор A, содержащий n натуральных чисел, как найти наименьшее целое число> = 0 , которое можно получить, используя все элементы в наборе.Каждый элемент может быть либо добавлен, либо вычтен к итогу.Несколько примеров, чтобы прояснить это.

A = [ 2, 1, 3]

Result = 0 (2 + 1 - 3)

A = [1, 2, 0]

Result = 1(-1 + 2 + 0)

A = [1, 2, 1, 7, 6]

Result = 1 (1 + 2 - 1 - 7 + 6)

1 Ответ

2 голосов
/ 21 апреля 2011

Вы можете решить эту проблему, используя булево целочисленное программирование. Существует несколько алгоритмов (например, Gomory или Branch and Bound) и бесплатные библиотеки (например, LP-Solve).

Рассчитайте сумму списка и назовите ее s. Удвойте числа в списке. Скажем, удвоенные числа a, b, c. Тогда у вас есть следующая система уравнений: 

Boolean x,y,z 

a*x+b*y+c*z >= s

Minimize ax+by+cz!

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

[Изменить]

Следует отметить, что преобразованную проблему можно рассматривать как " проблема с рюкзаком ": 

Boolean x,y,z 

-a*x-b*y-c*z <= -s

Maximize ax+by+cz!
...