#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* Generate random profits for n houses. For each house, the profit is
   an integer in the range [1...M]. */
int *genProfits ( int n, int M )
{
   int i, *P;

   P = (int *)malloc(n * sizeof(int));
   for (i=0; i<n; ++i) P[i] = 1 + rand() % M;
   printf("Profits are ");
   for (i=0; i<n; ++i) printf("%d ", P[i]);
   printf("\n");
   return P;
}

/* Calculate the total profit from all houses */
int totalProfit ( int *P, int n )
{
   int i, sum = 0;
   for (i=0; i<n; ++i) sum += P[i];
   return sum;
}

/* Generate and return the dynamic-programming table, given the profit
   array P[] (of size n) and the total profit T as input. */
int **genTable ( int *P, int n, int T )
{
   int i, j, **A;

   /* Allocate memory to the dynamic-programming table A */
   A = (int **)malloc(n * sizeof(int *));
   for (i=0; i<n; ++i) A[i] = (int *)malloc((T+1) * sizeof(int));

   /* Note: A[i][j] stores the possibility of achieving a profit of j
      from a subset of houses 0,1,2,...,i.
      A[i][j] = 0 meand "Profit j is unachievable from houses 0,1,2,...,i".
      A[i][j] = 1 means "Profit j is achievable from houses 0,1,2,...,i-1".
      A[i][j] = 2 means "Profit j is achievable but House i must be included
                        in the subset". */

   /* Initialize the first row of A:
      A[0][j] = 0 unless j = 0 (zero profit means no houses), or
      j = P[0] (House 0 gives this profit). */
   for (j=0; j<=T; ++j) A[0][j] = 0;
   A[0][0] = 1; A[0][P[0]] = 2;

   /* Include houses one by one */
   for (i=1; i<n; ++i) {
      for (j=0; j<=T; ++j) {
         if (A[i-1][j]) A[i][j] = 1;
         else if ((j >= P[i]) && (A[i-1][j-P[i]])) A[i][j] = 2;
         else A[i][j] = 0;
      }
   }
   /* Print the matrix A[][]. Needed only for debugging. */
   /* for (i=0; i<n; ++i) {
      for (j=0; j<=T; ++j) printf("%d",A[i][j]);
      printf("\n");
   } */
   return A;
}

/* This function returns the total profit to be achieved by the first son,
   given that the imbalance is as small as possible. The d-p array A[][]
   and its dimensions n and T are supplied as inputs. */
int firstSum ( int **A, int n, int T )
{
   int imbal1, imbal2, j1, j2;

   /* The more we move away from the following values, the more is the
      imbalance. So we locate the nearest achievable profits on the two
      sides of 2T/3. */
   j1 = 2 * T / 3; j2 = j1 + 1;

   /* j1 stores the best achievable allocation with S1 - 2*S2 negative */
   while (A[n-1][j1] == 0) --j1;
   imbal1 = 2 * (T - j1) - j1;

   /* j2 stores the best achievable allocation with S1 - 2*S2 positive */
   while (A[n-1][j2] == 0) j2++;
   imbal2 = j2 - 2 * (T - j2);

   /* Return the better of the two best cases */
   return ((imbal1 <= imbal2) ? j1 : j2);
}

/* Given the d-p array A[][], the first son's total profit S, and
   the profit array P[] of n houses, this function makes one possible
   division of houses to the two sons. */
void printAlloc ( int **A, int S, int *P, int n )
{
   int *B, i;

   /* The array B is meant for storing the allocation status of houses. */
   B = (int *)malloc(n*sizeof(int));

   /* Initially, allocate all houses to the second son. */
   for (i=0; i<n; ++i) B[i] = 2;

   /* Now, find out which houses will actually be assigned to the first son. */
   i = n-1;
   while (S > 0) { /* so long as the first son has received the total profit S */
      if (A[i][S] == 2) {
         /* Allocate this house to the first son. By construction of A[][],
            the profit S cannot be achieved from houses 0,1,2,...,i without
            including House i. */
         B[i] = 1; S = S - P[i]; --i;
      } else if (A[i][S] == 1) {
        /* The profit S can be achieved from houses 0,1,2,...,i-1. */
        --i;
      } else printf("There is a bug in your code...\n");
   }
   printf("First son gets houses   ");
   for (i=0; i<n; ++i) if (B[i] == 1) printf("%d ", i);
   printf("\n");
   printf("Second son gets houses  ");
   for (i=0; i<n; ++i) if (B[i] == 2) printf("%d ", i);
   printf("\n");
   free(B);
}

/* Free all dynamically allocated memory */
void windUp ( int *P, int **A, int n )
{
   int i;

   free(P);
   for (i=0; i<n; ++i) free(A[i]);
   free(A);
}

int main ( int argc, char *argv[] )
{
   int n, M, T, S1, S2;
   int *P, **A;

   srand((unsigned int)time(NULL));
   if (argc == 3) {
      n = atoi(argv[1]); M = atoi(argv[2]);
   } else {
      printf("Enter number of houses (n) : "); scanf("%d", &n);
      printf("Enter profit bound (M)     : "); scanf("%d", &M);
   }
   P = genProfits(n,M);
   T = totalProfit(P,n);
   A = genTable(P,n,T);
   S1 = firstSum(A,n,T); S2 = T - S1;
   printf("Profit for first son  : %d\n", S1);
   printf("Profit for second son : %d\n", S2);
   printf("Imbalance (S1 - 2*S2) : %d\n", S1 - 2 * S2);
   printAlloc(A,S1,P,n);
   windUp(P,A,n);
   exit(0);
}