#include <stdio.h> 
 
#include "heure.h" 
 
static int N; 
static heure* valeur; 
static bool* ok; 
static bool* solution; 
static heure seuil; 
static heure grand_total; 
 
//------------------------------------------------------ 
void permutations (int valeurs, int possibilites, int pos = 0) 
//------------------------------------------------------ 
{ 
	if (valeurs <= 0) 
	{ 
		// c'est la fin 
		heure total; 
		int k; 
 
		// On calcule le total des valeurs marquees 
 
		for (k = 0; k < N; k++) 
		{ 
			if (ok[k]) total += valeur[k]; 
		} 
 
		if (total <= seuil) 
		{ 
			if (total > grand_total) 
			{ 
				// nouveau total 
				grand_total = total; 
				 
				for (k = 0; k < N; k++) 
				{ 
					solution[k] = ok[k]; 
				} 
			} 
			else 
			{ 
				// pas mieux 
			} 
		} 
		else 
		{ 
			// trop grand 
		} 
		 
		return; 
	} 
 
	// Protection : ca ne devrait jamais arriver !!! 
	if (valeurs > possibilites) return; 
 
	// On essaie en utilisant la première case 
	ok[pos] = true; 
	permutations (valeurs-1, possibilites-1, pos+1); 
 
	// On essaie en n'utilisant pas la première case 
	ok[pos] = false; 
	permutations (valeurs, possibilites-1, pos+1); 
} 
 
//------------------------------------------------------ 
int main (int argc, char* argv[]) 
//------------------------------------------------------ 
{ 
	// Recuperation des parametres 
	// 
	//  Le premier est le seuil 
	argc--; 
	argv++; 
 
	seuil = argv[0]; 
 
	//  Ensuite on a N valeurs 
	argc--; 
	argv++; 
 
	N = argc; 
 
	valeur   = new heure[N]; 
 
	int k; 
 
	for (k = 0; k < N; k++) 
	{ 
		valeur[k] = argv[0]; 
		argc--; 
		argv++; 
	} 
 
	// On a besoin de N etats pour cocher les valeurs. 
	// Et d'une copie pour la solution. 
	ok       = new bool[N]; 
	solution = new bool[N]; 
 
	// On essaie les permutations successivement pour 
	// des nombres de valeurs de + en + grands parmi N 
	for (k = 1; k <= N; k++) 
	{ 
		permutations (k, N); 
	} 
	 
	for (k = 0; k < N; k++) 
	{ 
		valeur[k].print (); 
		if (solution[k]) printf (" <--- "); 
		printf ("\n"); 
	} 
	printf ("-----\n"); 
	grand_total.print (); 
	printf ("\n"); 
	 
	return (0); 
}