/* GPL Licenced
 * This app packackages a package with
 * some algorithmes*/

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

struct package {
	char * name [100];
	int prior;
	int weight;
	int take;
};

#define MAX_SIZE 10
struct package pack [MAX_SIZE];
int size;
int maxweight = 1000;

void print_field ()
{
	int i,ges=0;
	
	printf ("Name\tPrior\tWeight\n");
	for (i=0; i<size; i++)
	{
		if (pack[i].take == 0)
			continue;
		printf ("%s\t%d\t%d\n", pack[i].name,
			(int) pack[i].prior,
			(int) pack[i].weight);
		ges += pack[i].prior;
	}
	printf ("Gesamt: %d\n", ges);
}

void read_field ()
{
	int ret;
	
	for (size=0; size < MAX_SIZE; size++)
	{
		ret = fscanf (stdin, "%s%d%d",
			pack[size].name, 
			&pack[size].prior, 
			&pack[size].weight);
		pack[size].take = 0;
		if (ret != 3)
			break;
	}
}

void swap (int i, int j)
{
	struct package temp;
	temp = pack[i];
	pack [i] = pack[j];
	pack [j] = temp;
}

int compare (const void *v1, const void *v2)
{
	struct package * t1 = (struct package*) v1;
	struct package * t2 = (struct package*) v2;

	if (t1->prior/t1->weight < t2->prior/t2->weight)
		return 1;
	else if (t1->prior/t1->weight > t2->prior/t2->weight)
		return -1;
	else return 0;
}

void sort_fast ()
{
	int i,w=0;
	qsort (pack, size, sizeof (struct package), compare);
	for (i=0; i< size; i++)
	{
		w += pack[i].weight;
		if (w > maxweight) 
			w-= pack[i].weight;
		else 
			pack[i].take = 1;
	}
}

int maxcost;
int bestx;

void sort_enumerate (int z, int *x)
{
	int i,j;
	int * t;
	int xcost=0, xweight=0;
	
	for (i=0; i<size;i++) 
		if (x[i])
			xweight+=pack[i].weight;
	for (i=0; i<size;i++)
		if (x[i])
			xcost+=pack[i].prior;

	if (xweight <= maxweight)
	{
		if (xcost > maxcost)
		{
			maxcost = xcost;
			for (j=0;j<size;j++)
				pack[j].take = x[j];
			/*
			printf ("#%d %d:%d\n",z,xweight, xcost);
			print_field ();*/
		}
		for (i=z+1; i<size; i++)
		{
			x[i] = 1;
			t = malloc (MAX_SIZE*sizeof(int));
			memcpy (t,x, MAX_SIZE*sizeof(int));
			sort_enumerate (i,t);
			free (t);
			x[i] = 0;
		}
	}
}

int main ()
{
	int * f;
	int i;

	read_field();
	
	f=malloc (MAX_SIZE*sizeof(int));
	for (i=0; i< MAX_SIZE; i++)
		f[i] = 0;
	sort_enumerate(0,f);
	// sort_fast();
	
	printf ("Lösung:\n");
	print_field();
	return 0;
}