Le problème du sac à dos

On dispose d’un sac à dos, ne pouvant supporter plus d’un certain poids, et d’un ensemble d’objets ayant chacun un poids et une valeur.
Le problème du sac à dos consiste à remplir le sac avec les objets pour que la valeur des objets mis dans le sac à dos soit maximisée, sans dépasser le poids maximum.

Le problème du sac à dos

Quels objets choisir pour obtenir une valeur maximale sans dépasser 30 kg ?

Objet	A	B	C	D
valeur	7 €	4 €	3 €	3 €
poids	13 kg	12 kg	8 kg	10 kg

Le problème du sac à dos

Quels objets choisir pour obtenir une valeur maximale sans dépasser 2348 kg ?

Objet	A	B	C	D	E	F
valeur	96 €	76 €	56 €	11 €	89 €	10 €
poids	209 kg	692 kg	333 kg	92 kg	638 kg	188 kg

Objet	G	H	I	J	K	L
valeur	66 €	83 €	12 €	9 €	81 €	45 €
poids	360 kg	734 kg	238 kg	160 kg	380 kg	840 kg

Le problème du sac à dos

Quels objets choisir pour obtenir une valeur maximale sans dépasser 2348 kg ?

Objet	A	B	C	D	E	F
valeur	96 €	76 €	56 €	11 €	89 €	10 €
poids	209 kg	692 kg	333 kg	92 kg	638 kg	188 kg
Valeur / Poids	0.459	0.109	0.168	0.119	0.139	0.053

Objet	G	H	I	J	K	L
valeur	66 €	83 €	12 €	9 €	81 €	45 €
poids	360 kg	734 kg	238 kg	160 kg	380 kg	840 kg
Valeur / Poids	0.183	0.113	0.050	0.056	0.213	0.053

Le problème du sac à dos

Quels objets choisir pour obtenir une valeur maximale sans dépasser 2348 kg ?

Objet	A	K	G	C	E	D	F
valeur	96 €	81 €	66 €	56 €	89 €	11 €	76 €
poids	209 kg	380 kg	360 kg	333 kg	638 kg	92 kg	692 kg
Valeur / Poids	0.459	0.213	0.183	0.168	0.139	0.119	0.109

Objet	H	J	L	B	I
valeur	83 €	9 €	45 €	10 €	12 €
poids	734 kg	160 kg	840 kg	188 kg	238 kg
Valeur / Poids	0.113	0.056	0.053	0.053	0.050

Le problème du sac à dos

La résolution est-elle toujours optimale ?

Le problème du sac à dos

Quels objets choisir pour obtenir une valeur maximale sans dépasser 15 kg ?

Objet	A	B	C	D
valeur	70 €	40 €	35 €	36 €
poids	10 kg	8 kg	7 kg	9 kg

Quels objets choisir pour obtenir une valeur maximale sans dépasser 15 kg ?

Objet	A	B	C	D
valeur	70 €	40 €	35 €	36 €
poids	10 kg	8 kg	7 kg	9 kg
Valeur / Poids	7	5	5	4

Le rendu de monnaie

On veut programmer une caisse automatique pour qu’elle rende la monnaie de façon optimale, c’est-à-dire avec le nombre minimal de pièces et billets. La valeur des pièces et billets à disposition sont : 1, 2, 5, 10, 20, 50, 100 et 200 euros.
On dispose d’autant d’exemplaires qu’on le souhaite de chaque pièce et billet.

Le rendu de monnaie

Anaïs veut acheter un objet qui coûte 53 euros. Elle paye avec un billet de 100 euros. La caisse automatique doit lui rendre 47 euros.
Quelle est la meilleur façon de rendre la monnaie ?

Le rendu de monnaie

Ecrire un algorithme qui permet de rendre la monnaie de manière efficace