Problème du sac à dos

sac_a_dos.c

// Sac à dos.cpp : Defines the entry point for the console application.
//

#include "stdafx.h" // Pour printf
#include <time.h> // Pour générer de l'aléatoire et calculer le temps utilisé par la fonction
#include <stdlib.h> // Pour system("pause")

#define NBR_OBJETS 25 // Le nombre d'objets à générer

int main()
{
	float objets[NBR_OBJETS]; // Une liste d'objets
	int capacite; // La capacite du sac
	float max = 0.0; // La masse de la meilleure combinaison
	int best; // La meilleure combinaison
	int i, n; // Utilisé pour les for
	float sum; // La masse de la combinaison actuelle
	int toshow; // Le nombre de caractère "#" à afficher dans la progress-bar
	srand(time(NULL)); // Génération d'une pseudo-liste aléatoire en fonction de maintenant.

	/*Remplissage de la liste d'objet par des objets de masse allant de 0.01 à 9.99 inclus*/
	for (i = 0; i < NBR_OBJETS; i++) {
		objets[i] = (float)(rand() % 999 + 1) / 100;
		if (objets[i] > max) max = objets[i];
	}
	/*Calcule d'une capacité pouvant aller de 2x à 4x la masse du plus lourd objet*/
	capacite = (int)(max * (2 + rand() % 20 / 10));

	/*Affichage de la liste d'objet et de la capacité du sac*/
	printf("Selon les %d objets suivants: ", NBR_OBJETS);
	for (i = 0; i < NBR_OBJETS; i++) printf("%.2f ", objets[i]);
	printf("\nEt un sac de capacite suivante: %d\n\n", capacite);

	/*Sauvegarde du moment de démmarage de l'algorythme, affichage d'une progress-bar vide*/
	time_t seconds = time(NULL);
	printf("\t[                    ]\r");

	/*
		Codification des objets sur 2^length(objets) bits.
		Addition de chaque objets étant bit à bit égal avec la conversion binaire de i
		Sauvegarde de la liste d'objet (et de sa masse totale) si c'est une meilleure combinaison
		Mise à jour de la progress-bar
	*/
	for (i = 1; i < (1 << NBR_OBJETS); i++) {
		/*Addition*/
		sum = 0; // Reset de la somme
		for (n = 0; n < NBR_OBJETS; n++) {
			if (((1 << n) & i) > 0) sum += objets[n];
		}

		/*Test et sauvegarde*/
		if (sum <= capacite && sum > max) { // Si meilleure masse
			max = sum; // Sauvegarde de la masse totale
			best = i; // Sauvegarde de la combinaison d'objet
		}

		/*Mise à jour*/
		if (i % (1 << (NBR_OBJETS - 5)) == 0) {
			printf("\t[");
			toshow = (int)((float)(i + 1) / (float)(1 << (NBR_OBJETS)) * 20);
			for (n = 0; n <= toshow; n++) {
				printf("#");
			}
			for (n = 1; n < 20 - toshow; n++) {
				printf(" ");
			}
			printf("]\r");
		}
	}

	/*Affichage des résulats*/
	printf("\n\nLa serie d'objet qui remplie au mieux le sac est la suivante: ");
	for (i = 0; i < NBR_OBJETS; i++) if (((1 << i) & best) > 0) printf("%.2f ", objets[i]);
	printf("\nPour une capacite totale de %.2f/%d", max, capacite);
	printf("\n\nTemps ecoule: %d secondes\n", time(NULL) - seconds);
	system("pause");
}