Efficiently tracing the sum of sets from balanced subset sum?

Question

Balanced subset sum problem is described as to divide array into two subsets such that difference of sum of two sub sets is minimum, Best case will be when sum of two subsets are equal.

Note: - We can not leave elements from the original set .

Now i need to get the sum of set 1 and set 2 for the minimum difference partitioning, I have already found the sum of sets using a O(sum*sum*n) solution , but for the purpose of what I am doing i need something with a better complexity. How can this be solved in less time than O(sum*sum*n)?

My O(N^3) approach is as under: Note : -s1,s2,s3 are static variables,sum being the sum of array.

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; } }

I don't claim to understand your code, but this is a NPC problem, so it would be a real surprise for a polynomial algorithm to solve it. So either your algorithm or your estimation of the running time are not wrong. — ead
– ead, Commented Feb 16, 2016 at 20:49
@ead elements are not exceeding 225 and maximum no. of elements are 20 . — A. Sam
– A. Sam, Commented Feb 17, 2016 at 5:09

ead · Accepted Answer · 2016-02-17 08:03:33Z

I think you should use a pseudo-polynomial algorithm which runs in O(sum*n), albeit the proposal in comments to use O(2^ n) brute force approach should work as well.

The idea is similar to pseudo-polynomial algorithm for knapsack: find all possible partitions with combined value less or equal MAX=sum/2. The biggest of these partitions will be the one you are looking for.

Here is a possible implementation in 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

Collectives™ on Stack Overflow

Efficiently tracing the sum of sets from balanced subset sum?

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related