#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];
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 );
}
void	best_fit( void )
{
	int	i;
	if( n_sol == n_max || n_sol == n_elenco )
	{
		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
	{
		for( i = 0; i < n_elenco; i++ )
		{
			if( usato[i] == 0 )
			{
				usato[i] = 1;
				sol[n_sol++] = i;
				val_sol += elenco[i].valore;
				peso_sol += elenco[i].peso;
				best_fit();
				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 );
}