Эффективное отслеживание суммы множеств из суммы сбалансированных подмножеств?

Question

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

Примечание: - Мы не можем оставлять элементы оригинального набора.

Теперь мне нужно получить сумму набора 1 и набор 2 для минимальной разницы разбиения, я уже нашел сумму множеств с помощью O(sum*sum*n) решения, но с целью того, что я делаю, мне нужно что-то с лучшей сложностью. Как это можно решить за меньшее время, чем O(sum*sum*n)?

Мой подход O (N^3) таков: Примечание: -s1, s2, s3 являются статическими переменными, сумма которых является суммой массива.

static int partition(int sum1, int sum2, ArrayList <Integer> arr, int i) { 
if (i == arr.size()) { 
    if (Math.abs(sum1 - sum2) < s3) { 
    s1 = sum1; 
    s2 = sum2; 
    s3 = Math.abs(sum1 - sum2); 
    } 

    return Math.abs(sum1 - sum2); 

} 
if (dp[(sum1 < 0) ? 2 * sum - sum1 : sum1][(sum1 < 0) ? 2 * sum - sum1 : sum1][i] != 0) 
    return dp[(sum1 < 0) ? 2 * sum - sum1 : sum1][(sum1 < 0) ? 2 * sum - sum1 : sum1][i] > 0 ? dp[(sum1 < 0) ? 2 * sum - sum1 : sum1][(sum1 < 0) ? 2 * sum - sum1 : sum1][i] - 1 : dp[(sum1 < 0) ? 2 * sum - sum1 : sum1][(sum1 < 0) ? 2 * sum - sum1 : sum1][i]; 


int c1 = partition(sum1 + arr.get(i), sum2, arr, i + 1); 
int c2 = partition(sum1, sum2 + arr.get(i), arr, i + 1); 

if (Math.abs(c1) < Math.abs(c2)) { 
    dp[(sum1 < 0) ? 2 * sum - sum1 : sum1][(sum1 < 0) ? 2 * sum - sum1 : sum1][i] = c1 >= 0 ? c1 + 1 : c1; 
    return c1; 
} else { 
    dp[(sum1 < 0) ? 2* sum - sum1 : sum1][(sum1 < 0) ? 2 * sum - sum1 : sum1][i] = c2 >= 0 ? c2 + 1 : c2; 
    return c2; 
} 

} 

Answer 1

Я думаю, вы должны использовать pseudo-polynomial алгоритм, который работает в O(sum*n), хотя предложение в комментариях, чтобы использовать O(2^ n) грубой силы подход должен работать.

Идея похожа на pseudo-polynomial algorithm for knapsack: найти все возможные перегородки с комбинированным значением не более MAX=sum/2. Самый большой из этих разделов будет тот, который вы ищете.

Вот возможная реализация в Python:

def min_partition_diff(items): 
    summed=sum(items) 
    MAX=summed//2 


    value_reachable=[False]*(MAX+1)  
    value_reachable[0]=True #at the beginning only the empty set with value 0 is reachable 

    #update all possible configurations: 
    for item in items: 
     for i in reversed(range(MAX)):# //backwards->object at most once in every configuration! 
      if value_reachable[i]:#update configuration only if it can be constructed with earlier items 
       next_reachable_value = i+item 
       if next_reachable_value <= MAX: 
        value_reachable[next_reachable_value]=True 

    biggest_value_possible=MAX - value_reachable[::-1].index(True)# find last True in the values 

    return summed-2*biggest_value_possible # this is the smallest difference