Блог

Учитывая набор S из n положительных целых чисел, мы хотим знать, можем ли мы найти комбинацию знаков для каждого из чисел в S ( или -), такую, что сумма S равна 0.

Как можно эффективно решить эту проблему? Основываясь на аналогичных проблемах, я бы предположил, что необходимо какое-то динамическое программирование. Есть ли какая-либо литература по этой конкретной проблеме (мне трудно ее найти).

Я предполагаю, что это похоже на проблему с суммой подмножеств. Однако теперь мы должны использовать весь набор, и для каждого целого числа s _i мы можем включить-s _i или s _i, но не оба.

Учитывая, что проблема, по-видимому, является NP-полной, лучшим выбором является использование решателя SAT, MILP, CP или ASP, поскольку они предназначены для решения такого рода проблем.

Решение

Вот решение с использованием ASP (Программирование набора ответов).

Дано досье instance.lp :

 value(12).
value(12).
value(1).
value(2).
value(3).
value(5).
value(6).
value(7).
 

и файл encoding.lp :

 % every value can be positive (or not)
{pos(X)} :- value(X).

% fail if the sum is not 0
:- not 0 = #sum {V : pos(V); -V : not pos(V), value(V)}.

% format output
#show pos/1.
#show neg(V) : not pos(V), value(V).
 

проблема может быть решена с помощью clingo,
решателя ASP из коллекции инструментов potassco (легко устанавливается через conda, pip, Ubuntu Package Manger и т. Д.).

Зовущий:

 clingo instance.lp encoding.lp
 

дает вам результат:

 Answer: 1
pos(1) pos(2) pos(3) pos(5) pos(7) neg(6) neg(12)
 

Вы можете перечислить все возможные решения с помощью:

 clingo instance.lp encoding.lp 0
 

даю тебе

 Answer: 1
pos(1) pos(2) pos(3) pos(5) pos(7) neg(6) neg(12)
Answer: 2
pos(2) pos(3) pos(6) pos(7) neg(5) neg(1) neg(12)
Answer: 3
pos(5) pos(6) pos(7) neg(3) neg(2) neg(1) neg(12)
Answer: 4
pos(12) pos(1) pos(2) pos(3) neg(7) neg(6) neg(5)
Answer: 5
pos(12) pos(6) neg(7) neg(5) neg(3) neg(2) neg(1)
Answer: 6
pos(12) pos(1) pos(5) neg(7) neg(6) neg(3) neg(2)
 

гадюка

Использование ASP для решения проблемы имеет то преимущество, что:

• быть легко ремонтопригодным (очень краткое описание проблемы, легко читается)
• очень быстро (на основе SAT и CDNL)
• декларативный (вы описываете только проблему, а не то, как ее решить)
• легко расширяемый с другими ограничениями
• также способен выполнять все виды оптимизации (например, оптимизировать для самого большого подмножества, чтобы сформировать сумму)

Редактировать Вы также можете скопировать и вставить содержимое обоих файлов, чтобы самостоятельно проверить результаты онлайн, используя js-компиляцию clingo здесь

Решение этой проблемы связано с проблемой суммы подмножеств.

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

Вот код на c :

 #include<stdio.h>

int arr[] = {1, 2, 2, 3, 4};
int n = 5; // size of arr
int sum = 0;

// dp array only needs to be [n   1][total sum   1] big
bool dp[30][100];
inline void subset_sum(){
    for (int i = 0; i <= sum; i  )
        dp[0][i] = false;

    for (int i = 0; i <= n; i  )
        dp[i][0] = true;

    for (int i = 1; i <= n; i  ) {
        for (int j = 1; j <= sum; j  ) {
            dp[i][j] = dp[i - 1][j];
            if (arr[i - 1] <= j)
                dp[i][j] |= dp[i - 1][j - arr[i - 1]];
        }
    }
}
int main(){
    for (int i = 0; i < n; i  )
        sum  = arr[i];

    // run subset sum dp using a bottom-up approach
    // True = sum is possible, False = not possible
    subset_sum();

    int max_half;
    for (int i = sum / 2; i>=1; i--){
        if (dp[n][i]){ // it is possible to sum to i using values in arr
            max_half = i;
            break;
        }
    }

    // output will be the closest sum of positives
    // and negatives to 0
    printf("%dn", 2 * max_half - sum);

    return 0;
}
 

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

Из 2 * max_half - sum этого можно вывести max_half - (sum - max_half) , что было бы нашей наилучшей возможной суммой за вычетом остальных чисел.

Вот несколько примеров различных наборов чисел и их соответствующих выходных данных:

Набор: {1, 2, 2, 3, 4} , вывод: 0 .

Набор: {1, 1, 1, 1, 1} , вывод: -1 .

Набор: {5, 2, 6, 8, 9, 2} , вывод: 0 .

Набор: {1, 50} , вывод: -49 .

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

Временная сложность этого кода равна O(n * сумма), а пространственная сложность равна O(n * сумма).

Также можно пожертвовать некоторой временной сложностью, чтобы улучшить пространственную сложность, используя 1-мерный массив dp.