SPOJ PARTY Solution

| July 01, 2015

The correct, optimal and working solution for programming question PARTY on spoj

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

#define DEBUG 0

int max ( int a , int b ) {
	return a > b ? a : b;
}

int main ( int argc , char * argv[] ) {


	while ( 1 ) {

	int budget , n , i , j;
	scanf("%d%d" , &budget , &n);

	if ( budget == 0 && n == 0 )
		break;

	int **array = (int **) calloc( sizeof(int *) , n+1 );
	for ( i = 0 ; i < n+1 ; i++ ) {
		array[i] = (int *) calloc ( sizeof(int) , budget+1 );
	}

	int * fun = (int *) malloc ( n * sizeof(int));
	int * fee = (int *) malloc ( n * sizeof(int));

	for ( i = 0 ; i < n ; i++ ) {
		scanf("%d%d" , &fee[i] , &fun[i]);
	}

	#if DEBUG
		printf("Budget:%d\n" , budget);
		printf("Number of parties:%d\n" , n);
		for ( i = 0 ; i < n ; i++ ) {
			printf("Party %d: Fee -> %d and fun -> %d\n" , i , fee[i] , fun[i]);
		}
	#endif

	for ( i = 1 ; i < n+1 ; i++ ) {
		for ( j = 1 ; j < budget+1 ; j++ ) {
			if ( fee[i-1] <= j ) {
				//array[i][j] = max ( array[i-1][j] , array[i-1][j-fee[i-1]] + fun[i-1] );

				int tn = array[i-1][j];
				int ts = array[i-1][j-fee[i-1]] + fun[i-1];
				if ( tn > ts ) {
					array[i][j] = tn;
				}
				else {
					array[i][j] = ts;
				}
			}
			else
				array[i][j] = array[i-1][j];
		}

	}

	#if DEBUG
		printf("Matrix:\n");
		for ( i = 0 ; i < n+1 ; i++ ) {
			for ( j = 0 ; j < budget+1 ; j++ ) {
				printf("%d " , array[i][j]);
			}
			printf("\n");
		}
	#endif

	i = budget;
	while ( array[n][i-1] == array[n][i] ) {
		i--;
	}

	printf("%d %d\n" , i , array[n][budget] );

	for ( i = 0 ; i < n+1 ; i++ ) {
		free(array[i]);
	}
	free(array);
	free(fee);
	free(fun);

	}

	return 0;
}