Divide the given array into two subsets S1 and S2 such that sum(S1)-sum(S2) is minimum

#include <stdio.h>
#include <string.h>

#define MIN2(a, b) ((a) < (b) ? (a) : (b))
#define MIN4(a, b, c, d) MIN2(MIN2(a, b), MIN2(c, d))

/*Int comparator for sorting*/
int compareInt(const int *a, const int *b)
{
return *a - *b;
}

/*
This function divides the given array into two parts such that difference of their sum is minimum

Algo:
1. sort the array
2. Starting from the end, put last element into one part and last two into another part
3. From k = n-2 to 0, compare diffs of
    a. smaller part + a[k] and bigger part
    b. smaller part + last num of bigger part and bigger part - last num of bigger part + a[k]
    c. smaller part - last num of smaller part + last num of bigger part and bigger part - last num of bigger part + a[k] + last num of smaller part
    d. smaller part - last num of smaller part + last num of bigger part + a[k] and bigger part - last num of bigger part + last num of smaller part

4. if a is small, add k to smaller part
    else if b is small add last number of bigger part to smaller part and a[k] to bigger part
    else swap last parts and
      if c is small add a[k] to bigger
      else add a[k] to smaller
*/
void divide(int a[], int n)
{
int i;

/*print the given array*/
printf("\n\nGiven array: ");

for(i = 0; i <n; ++i)
printf("%d ", a[i]);

printf("\n\n");

/*sort the array*/
qsort(a, n, sizeof(int), compareInt);


/*struct to hold info about each part*/
typedef struct
{
int arr[n];
int index;
int sum;
}Part;


/*Initialize two parts*/
Part b, c;

memset(&b, 0, sizeof(b));
memset(&c, 0, sizeof(c));

b.arr[0] = a[n-1];
c.arr[0] = a[n-2];

b.index = 0;
c.index = 0;

b.sum = a[n-1];
c.sum = a[n-2];

int k = n-3;
int diff1, diff2, diff3, diff4;
int lastOfSmaller, lastOfBigger, mn;

//pointers to smaller and bigger parts
Part *smaller, *bigger;

while(k >= 0)
{
//decide smaller and biggers parts
if(b.sum < c.sum)
{
smaller = &b;
bigger = &c;
}
else
{
smaller = &c;
bigger = &b;
}

//now decide where to put a[k] in smaller or bigger part
lastOfBigger = bigger->arr[bigger->index]; //last element of bigger
lastOfSmaller = smaller->arr[smaller->index]; //last element of smaller

diff1 = abs((smaller->sum + a[k]) - bigger->sum);
diff2 = abs((smaller->sum + lastOfBigger) - (bigger->sum - a[k] - lastOfBigger));
diff3 = abs((smaller->sum - lastOfSmaller + lastOfBigger) - (bigger->sum - lastOfBigger + lastOfSmaller + a[k]));
diff4 = abs((smaller->sum - lastOfSmaller + lastOfBigger + a[k]) - (bigger->sum - lastOfBigger + lastOfSmaller));

mn = MIN4(diff1, diff2, diff3, diff4);

if(mn == diff1)
{
smaller->arr[++smaller->index] = a[k];
smaller->sum += a[k];
}
else if(mn == diff2)
{
smaller->sum += lastOfBigger;
smaller->arr[++smaller->index] = lastOfBigger;

bigger->sum += a[k] - lastOfBigger;
bigger->arr[bigger->index] = a[k];
} else{
smaller->sum -= lastOfSmaller + lastOfBigger;
smaller->arr[smaller->index] = lastOfBigger;

bigger->sum -= lastOfBigger + lastOfSmaller;
bigger->arr[bigger->index] = lastOfSmaller;

if (mn == diff3) {
bigger->sum += a[k];
bigger->arr[++bigger->index] = a[k];
} else {
smaller->sum += a[k];
smaller->arr[++smaller->index] = a[k];
}
}

k--;
}

/*print the first part*/
int p = 0;

printf("Part1: ");
while(p <= b.index)
printf("%d ", b.arr[p++]);

printf("\n\n");

/*print the second part*/
p = 0;

printf("Part2: ");
while(p <= c.index)
printf("%d ", c.arr[p++]);

printf("\n\n");


printf("Sum Diff: %d\n\n", mn);
}

int main()
{
int a[] = {14, 9, 7, 6, 5, 3};
divide(a, sizeof(a)/ sizeof(int));
}
Advertisements

8 thoughts on “Divide the given array into two subsets S1 and S2 such that sum(S1)-sum(S2) is minimum

  1. Awesome answer…I appreciate the effort you take to write n build such a nice and efficient code..The logic of program has no bugs butSome suggestions to make it flawless,1)int compareInt(const int *a, const int *b){ return *a – *b;}should beint compareInt (const void * a, const void * b){ return ( *(int*)a – *(int*)b );}2) Missing #include directive algorithm.h to make qsort visible for compiler.3)You just cannot declare array with a variable size, so arr[(n+1)/2], in definition of Part struct,is incorrect..

  2. Can you please elaborate more on the partel = *(bigger->index); //last element of biggerdiff1 = smaller->sum + a[k] – bigger->sum;diff2 = smaller->sum +(el << 1)-bigger->sum-a[k];i cant get logic behind it..and why are you doing "e1 << 1" ??

  3. if the problem is "split the array into two set such that – how to implement it?the no. of elements of each set is equal or differ by 1 and also the sum diff. also min.

  4. diff2 = sum(smaller set + last element of bigger) – sum(bigger set + a[k] – last element of bigger) = smaller->sum + el – bigger->sum +el – a[k] = smaller->sum + 2*el – bigger->sum – a[k]2*el can also be written as el << 1.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s