Question

Suppose we are given a set ? containing 2? integers, and we wish to partition it into two sets ?1 and ?2 so that |?1 | = |?2 | = ? and so that the sum of the numbers in ?1 is as close as possible to the sum of those in ?2. Let the neighborhood ? be determined by all possible interchanges of two integers between ?1 and ?2. Is ? exact?

Answer 1

Here the given set S containing 2n integers, After partitioning each set contains n elements. and summation of the elements of s1 is as close as possible s2 means the difference is minimum when we subtract the sums of s1 and s2.

this can be achieved 1st compare one element of S1 with all the elements of S2 by using recursion .then compare elements of S2 with every element of S1.

Example: A={1,2,3,4} here we can divide it into S1={1,4} and S2={2,3} here 1+4=2+3.

example:2 if we need sum=8 then if an array contains 4 elements and we need to divide into equal partitions then if one element is 5 and another one must be 3 if one is 7 and another element is 1.so for each sum and formation partition.

As this can be achieved by using recursion or by using knapsack problem, there is no exact number of interchange because the sum can change from one problem to another and the number of elements in each subset change according to required example if S contains 6 elements each subset contain 3 elements .if S contains 8 elements then each subset contain 4 elements according to that to achieve sum the values of the elements also changed so it is depended on dynamic programming so there is no exact interchange in comparison.