Problème du sac à dos

denq · 27-03-2011 10:52:44

Quelqu'un l'a-t-il résolu?

extrait Wikipedia:"En algorithmique, le problème du sac à dos, noté également KP (en anglais, Knapsack Problem) est un problème d'optimisation combinatoire. Il modélise une situation analogue au remplissage d'un sac à dos, ne pouvant supporter plus d'un certain poids, avec tout ou partie d'un ensemble donné d'objets ayant chacun un poids et une valeur. Les objets mis dans le sac à dos doivent maximiser la valeur totale, sans dépasser le poids maximum."

http://fr.wikipedia.org/wiki/Probl%C3%A … %C3%A0_dos

Pascal35 · 27-03-2011 11:18:27

C'est pourtant simple, comment n'y ai-je pas penser plus tôt ?

Uploaded with ImageShack.us

Pascal35 · 30-03-2011 13:43:42

Après réflexion, je me dis que tu étais peut-être sérieux dans ta question, Denq.
C'est vrai qu'il y a de bons scientifiques sur le forum si j'en crois certains messages.
Quoiqu'ayant quelques connaissances en mathématiques, je suis clairement dépassé et mon message n'était qu'un essai (modeste et peut-être raté ) de faire un peu d'humour !

denq · 30-03-2011 13:59:48

Il y a sûrement matière à réflexion, quant à moi, je suis plutôt adepte du tâtonnement pifométrique!

Bison · 30-03-2011 15:04:27

C'est un problème qui est polynomial en N.

Si, si ...

antoinepierre · 30-03-2011 15:26:20

denq a écrit :

Il y a sûrement matière à réflexion, quant à moi, je suis plutôt adepte du tâtonnement pifométrique!

J'aime beaucoup cette philosophie.

lexxx · 30-03-2011 15:31:47

L'approche dans le problème du sac à dos est de savoir quel est le nombre maximum d'objets qu'on peut mettre dans un sac, sans que les bretelles ne lâchent sous le poids.
On optimise le nombre (à maxima), en se limitant sur le poids.
Exemple: mettre le plus de colis postaux dans un avion sans être en surcharge.

Le problème ici bas est plutôt de savoir comment minimiser le poids de ce que l'on emporte...
On optimise le poids (à minima), avec comme critère limitant (peut varier d'un individu à l'autre):
- la survie (1 slip de bain dans la neige, c'est un peu juste...),
- la sécurité,
- le volume du sac,
- ...

Pour le matériel, je vois moins d'intérêt à s’appesantir sur un problème d'optimisation que pour la nourriture.
Ça me rappelle le fichier Excel d'Olivier pour l'Islande.
Par exemple, j'essaie actuellement de réfléchir à partir une dizaine de jours en minimisant le volume de nourriture, parce que je n'ai pas envie d'acheter un nouveau sac à dos...

Ainsi, sur la base des divers apports d'une grande liste d'aliments, on pourrait imaginer écrire un problème d'optimisation du type:
On minimise le volume avec comme critère limitant:
- un apport journalier suffisant,
- un apport équilibré en protéines, glucides, lipides,
- une variété relative des repas (pour compliquer un peu l'affaire...),
- un poids total maximal: c'est là qu'on commence à s'amuser.
Et encore, là on n'a pas pris en compte l'aspect périssable des denrées...

On peut aussi inverser ce que je viens d'écrire et minimiser le poids tout en cherchant à limiter le volume.

Dernière modification par lexxx (30-03-2011 15:33:07)

Bison · 30-03-2011 15:34:30

AntoinePierre a écrit :

J'aime beaucoup cette philosophie.

C'est plus qu'une philosophie, c'est une science de l'ingénieur, enseignée à l'E.N.S.I.P.

Une bonne approximation vaut mieux qu'une fausse précision

Dernière modification par Bison (30-03-2011 15:35:57)

Bison · 30-03-2011 15:42:25

lexxx a écrit :

On minimise le volume avec comme critère limitant:
- un apport journalier suffisant,
- un apport équilibré en protéines, glucides, lipides,
- une variété relative des repas (pour compliquer un peu l'affaire...),
- un poids total maximal: c'est là qu'on commence à s'amuser.
Et encore, là on n'a pas pris en compte l'aspect périssable des denrées...

Problème résolu dans tous les sens
Arachides, noix de cajou, cernaux de noix.
500 g par jour => plus de 3.000 Cal.

Conservation sans problème, poids du contenant négligeable.

Bon, faut aimer, jour après jour ...

PS : plaquette de multivtamines, c'est ok aussi!

Dernière modification par Bison (30-03-2011 15:43:24)

Le forum de la randonnée légère ou ultra-légère !

#1 27-03-2011 10:52:44

Problème du sac à dos

#2 27-03-2011 11:18:27

Re : Problème du sac à dos

#3 30-03-2011 13:43:42

Re : Problème du sac à dos

#4 30-03-2011 13:59:48

Re : Problème du sac à dos

#5 30-03-2011 15:04:27

Re : Problème du sac à dos

#6 30-03-2011 15:26:20

Re : Problème du sac à dos

#7 30-03-2011 15:31:47

Re : Problème du sac à dos

#8 30-03-2011 15:34:30

Re : Problème du sac à dos

#9 30-03-2011 15:42:25

Re : Problème du sac à dos

Pied de page des forums