Minimum sum of numbers in an array
Source: Asked to me on quora ( cseblog.quora.com )
Problem:
Given an array of n positive numbers (n ~ 100000), what is the algorithmic approach to find the minimum possible sum (>=0) by using all the numbers in an array?
Example 1:
1 2 2 3 4
Answer : 0 (-1+2-2-3+4)
Example 2:
2 3 4 7 13
Answer: 1 (+2-3-4-7+13)
Solution:
Highlight the part between the * symbols for the answer.
* This is the partition problem: assigning +/- signs to use all numbers means splitting them into two groups; the minimum |sum| = S - 2T where S is the total and T is the largest subset sum not exceeding S/2.
Algorithm: subset-sum DP. Compute reachable sums up to floor(S/2) with a bitset: start with bit 0 set, and for each number x shift the bitset left by x and OR it in. The highest set bit T <= S/2 gives the answer S - 2T. Time O(n * S / 64) with bitset words, O(S) memory - fine when the values are bounded (the problem is NP-hard in general, so no algorithm polynomial in n alone exists unless P = NP; for huge values use the FPTAS or greedy heuristics).
Sanity checks: {1,2,2,3,4}: S = 12, best T <= 6 is 6 (2+4 or 1+2+3) -> 0. {2,3,4,7,13}: S = 29, best T <= 14 is 14 (7+4+3) -> 29 - 28 = 1. Matches the examples.
Note the tempting greedy "repeatedly subtract the two largest" (or heap balanced-assignment) is NOT always optimal - e.g. {8,7,6,5,4}: greedy gives 2, optimal is 0 (8+4 = 7+... 8+7 = 15, 6+5+4 = 15).
Solution by an Anonymous commenter (subset-sum/knapsack DP) from the comments; greedy counterexample and AI verification. *
Problem:
Given an array of n positive numbers (n ~ 100000), what is the algorithmic approach to find the minimum possible sum (>=0) by using all the numbers in an array?
Example 1:
1 2 2 3 4
Answer : 0 (-1+2-2-3+4)
Example 2:
2 3 4 7 13
Answer: 1 (+2-3-4-7+13)
Solution:
Highlight the part between the * symbols for the answer.
* This is the partition problem: assigning +/- signs to use all numbers means splitting them into two groups; the minimum |sum| = S - 2T where S is the total and T is the largest subset sum not exceeding S/2.
Algorithm: subset-sum DP. Compute reachable sums up to floor(S/2) with a bitset: start with bit 0 set, and for each number x shift the bitset left by x and OR it in. The highest set bit T <= S/2 gives the answer S - 2T. Time O(n * S / 64) with bitset words, O(S) memory - fine when the values are bounded (the problem is NP-hard in general, so no algorithm polynomial in n alone exists unless P = NP; for huge values use the FPTAS or greedy heuristics).
Sanity checks: {1,2,2,3,4}: S = 12, best T <= 6 is 6 (2+4 or 1+2+3) -> 0. {2,3,4,7,13}: S = 29, best T <= 14 is 14 (7+4+3) -> 29 - 28 = 1. Matches the examples.
Note the tempting greedy "repeatedly subtract the two largest" (or heap balanced-assignment) is NOT always optimal - e.g. {8,7,6,5,4}: greedy gives 2, optimal is 0 (8+4 = 7+... 8+7 = 15, 6+5+4 = 15).
Solution by an Anonymous commenter (subset-sum/knapsack DP) from the comments; greedy counterexample and AI verification. *
Since the array is large and unsorted (assumption), I think a greedy approach with backtracking is advisable.
ReplyDeleteMohan S N
This comment has been removed by the author.
DeleteAssuming that the numbers are integers, this problem can be solved using integer knapsack problem. Let the sum of all the numbers in the array be S. Think of a bag of size S/2. The problem now becomes making a subset from the array having sum less than or equal to S/2. Just be careful while obtaining S, as it might be larger than maximum allowed value for a positive integer. Use a proper database to hold that.
ReplyDeleteExactly !
DeleteAt every iteration, find the largest 2 integers in the array ('n' steps), remove and subtract them, and insert the difference back to the array. Do this 'n' times. We have the result in O(n^2) time.
ReplyDeletenice one :)
DeleteConsider the following example 3,3,3,7,8, 8
Deleteoptimal is 3+3+3+7-8-8 =0
But your method finds the optimal in the set 3,3,3,7,0 which is not 0 clearly.
So the method don't work if the largest 2 integers belong to same category
Replying to Sambhav Gupta's comment, find the largest 2 integers in the array ('n' steps), remove and subtract them, and insert the difference back to the array - That is the Karmarkar-Karp differencing heuristic - good in practice (and with a heap it is O(n log n)), but it is NOT always optimal: Anonymous's counterexample below (3,3,3,7,8,8) gives 0 by perfect partition while differencing leaves a remainder. For an exact answer you need the subset-sum DP. (Reply created using AI)
DeleteThis comment has been removed by the author.
DeleteAre we over estimating this problem ?
ReplyDeletehttp://www.quora.com/Given-an-array-of-n-positive-numbers-n-100000-what-is-the-algorithmic-approach-to-find-the-minimum-possible-sum-0-by-using-all-the-numbers-in-an-array/answer/Khalil-Sawant
i dont get the problem ... in example 1 where is -2 ?? all are positive numberz??
ReplyDeleteReplying to ADITYA P.'s comment, i dont get the problem ... in example 1 where is -2 ?? all are positive numberz?? - The numbers in the array are positive; YOU choose a sign for each when summing. Example 1 assigns -1+2-2-3+4 = 0. The task: pick signs to make the absolute total as small as possible. (Reply created using AI)
DeleteCreate the max heap (O(n)). Maintain two running counters. Take the first number from heap and add it to counter1, take the 2nd number form the heap and add it to counter2. After that, take the next number from the heap and add it to the counter that minimizes |counter1 - counter2|, i.e., always add that number to the counter that is currently smaller of the two. Keep doing this and you will get the answer in O(n log n). Proof: Is by induction...
ReplyDeleteRecursive Approach (inefficient though(2^n complexity) but I Like Recursion!):
ReplyDeleteint minsum(int* arr,int n, int m)//n is number of elements left to consider, m is the min sum
{
if(n==1)
{
if *arr>=m return *arr;
else return infinity;
int a=minsum(arr+1,n-1,m-*arr);
int b=minsum(arr+1,n-1,m+*arr);
return(a+*arr<b-*arr?a+*arr:b-*arr);
}
in main call minsum(arr,n,0)
Replying to timequalsmoney's comment, Recursive Approach (inefficient though(2^n complexity) but I Like Recursion!) - The recursion is correct but, as you note, exponential. Two upgrades: memoize on (index, current sum) to get the O(nS) DP, or note that reachable sums form a bitset you can shift-OR in O(S/64) per element - plenty fast for n = 100,000 if S is moderate. (Reply created using AI)
DeleteReplying to Unknown's comment, Assuming that the numbers are integers, this problem can be solved using integer knapsack problem - Correct. In subset-sum terms, set S to the total and search for the largest reachable sum T ≤ S/2; then the minimum absolute signed sum is S − 2T. A bitset DP computes reachability by shifting and OR-ing once per number. Its time and memory depend on S (pseudo-polynomial), so it is practical when the values and total are moderate, not merely because n is large or small. (Reply created using AI)
ReplyDelete