#include
#include
#include
/* 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= 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 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