Given a set of n distinct positive integers x1 x2 xn where

Given a set of n distinct positive integers x1, x2, ..., xn (where n is an even number) •(A) partition the set into two subsets each of cardinality n/2 such that the difference between the sums of the two subsets is maximized •(B) partition the set into two subsets such that the difference between the sums of the two subsets is minimized •Write an algorithm for (A) and estimate its resource requirements •Write an algorithm for (B) and estimate its resource requirements

Solution

Problem (A) can be solved by sorting all the integers x1,x2,....xn and put the n/2 smaller elements into one subset and remaining n/2 larger elements in another subset.But this costs O(nlogn) time.A better way is to find the maedian and use that integer to partition the two subsets.To find median we use Selection Algorithm.It takes only O(n) time.

Selection Algorithm:

Problem (B) can be solved by partitioning the set into size k and n-k and recording their sums.If we try all possible combinations then we can certainly find the minimum difference.

The algorithm needs O(2^n) time.

The other approach for (B) is using dynamic programming.

The problem can be solved using dynamic programming when the sum of the elements is not too big. We can create a 2D array dp[n+1][sum+1] where n is number of elements in given set and sum is sum of all elements. We can construct the solution in bottom up manner.

Algorithm: