/*
	Problema dello zaino.

	Trova l'insieme di pacchi che massimizzano il valore trasportato
	dato un limite massimo di pacchetti trasportabili.
*/
#define	MAX_ELENCO	100	/* Al piu` 100 pacchi */

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

typedef struct P {
	char	nome[20];	/* Nome del pacco */
	int	valore;		/* Valore del pacco */
	int 	peso;		/* Peso del pacco */
} PACCO;

PACCO	elenco[MAX_ELENCO];	/* Elenco pacchi, letto da file */
int	n_elenco;		/* Numero di pacchi nell'elenco */

int	sol[MAX_ELENCO];	/* Pacchi nella soluzione corrente */
int	n_sol;			/* Numero di pacchi nella soluzione */
int	val_sol;		/* Valore della soluzione */
int	peso_sol;		/* Peso della soluzione corrente */

int	best_sol[MAX_ELENCO];	/* Soluzione ottima */
int	n_best_sol;		/* Numero di pacchi nella soluzione ottima */
int	val_best;		/* Valore della soluzione ottima */
int	peso_best;		/* Peso della soluzione ottima */

int	n_max;			/* Numero massimo di pacchi ammissibili */

char	usato[MAX_ELENCO];	/* Vettore di supporto:
				   usato[i] = 0, il pacco i non e` nella sol.
				   esato[i] = 1, il pacco i e` nella sol. */

/*
	Legge da file l'elenco dei pacchi nel formato:
	Numero di pacchi nel file
	nome pacco 1	valore
	nome pacco 2	valore
	....
*/
void	read_elenco( char *s )
{
	FILE	*fp;
	int	i;

	if( (fp = fopen( s, "r" )) == NULL )
	{
		printf( "Impossibile aprire %s\n", s );
		exit( 1 );
	}

	fscanf( fp, "%d\n", &n_elenco );
	for( i = 0; i < n_elenco; i++ )
		fscanf( fp, "%s %d %d\n", elenco[i].nome,
				       &(elenco[i].valore),
				       &(elenco[i].peso) );
	fclose( fp );
}

/*
	Calcola ricorsivamento la soluzione ottima
*/
void	best_fit( void )
{
	int	i;

	/*
		Condizione di terminazione:
		1) Ho inserito nella soluzione un numero di pacchi
		   uguale al massimo richiesto
		2) Ho inserito nella soluzione tutti i pacchi a disposizione
		   nell'elenco letto da file
	*/
	if( n_sol == n_max || n_sol == n_elenco )
	{
		/*
			Se il valore della soluzione corrente e` piu`
			alto della soluzione migliore fino ad ora trovata,
			allora la soluzione corrente diventa la soluzione
			migliore
		*/
		if( val_sol > val_best || (val_sol == val_best && peso_sol <= peso_best) )
		{
			val_best = val_sol;
			peso_best = peso_sol;

			n_best_sol = n_sol;
			for( i = 0; i < n_sol; i++ )
				best_sol[i] = sol[i];
		}
	}
	else
	{
		/*
			Cerco nell'elenco dei pacchi, il primo
			pacco non ancora inserito nella soluzione
		*/
		for( i = 0; i < n_elenco; i++ )
		{
			if( usato[i] == 0 )
			{
				/*
					Inserisco il pacco nella soluzione:
					1) marco il pacco i come usato
					2) salvo il pacco i in sol
					3) aggiorno il valore della soluzione
				*/
				usato[i] = 1;
				sol[n_sol++] = i;
				val_sol += elenco[i].valore;
				peso_sol += elenco[i].peso;

				/*
					Procedo con un nuovo passo
					di ricerca
				*/
				best_fit();

				/*
					Tolgo il pacco i dalla soluzione.
				*/
				usato[i] = 0;
				n_sol--;
				val_sol -= elenco[i].valore;
				peso_sol -= elenco[i].peso;
			}
		}
	}
}

int	main( int argc, char **argv )
{
	int	i;

   printf("Inserisci il numero di pacchi: ");
   scanf("%d",&n_max);
	read_elenco( "zaino.txt" );

	/*
		La soluzione iniziale e` vuota
	*/
	peso_best = 0x7fff;
	val_best = 0;
	val_sol = 0;
	n_sol = 0;
	peso_sol = 0;
	for( i = 0; i < n_elenco; i++ )
		usato[i] = 0;

	/*
		Cerco la soluzione ottima
	*/
	best_fit();

	/*
		Stampo il risultato
	*/
	for( i = 0; i < n_best_sol; i++ )
		printf( "%s valore: %3d peso: %3d\n",
			elenco[best_sol[i]].nome,
			elenco[best_sol[i]].valore,
			elenco[best_sol[i]].peso );
	printf( "VALORE TOTALE: %3d PESO TOTALE: %3d\n", val_best,
							 peso_best );

   getch();
	return( 0 );
}