1

Bonjour,

J'ai l'impression que mon problème est pourtant simple, mais je n'arrive pas à trouver une piste de départ.

Mon problème :
J'ai un total T
J'ai une liste de valeurs connues.
Je cherche la combinaison linéaire de ces valeurs optimale qui me permettra d'atteindre au plus près le total T.

Avec une équation, je cherche à maximiser :
33186.png

Merci d'avance pour toute idée

2

Hmmm ça ne m'étonnerait pas que ça soit NP-complet, ce problème...

3

Ce n'est pas assimilable à une version unidimensionnelle du problème de rangement des colis (NP-complet, apparemment) dont on parlait y'a pas longtemps dans un autre topic ?
avatarZeroblog

« Tout homme porte sur l'épaule gauche un singe et, sur l'épaule droite, un perroquet. » — Jean Cocteau
« Moi je cherche plus de logique non plus. C'est surement pour cela que j'apprécie les Ataris, ils sont aussi logiques que moi ! » — GT Turbo

4

En effet, ça y ressemble en dimension 1 je pense.

Le lien du topic auquel tu penses à mon avis :
topics/118803-cherche-programme-plan-de-chargement#11

Effectivement, je pense que c'est un problème du type :
http://fr.wikipedia.org/wiki/Optimisation_lin%C3%A9aire_en_nombres_entiers#Optimisation_lin.C3.A9aire_en_nombres_entiers

5

Oui, c'est bien à ça que je pensais smile
avatarZeroblog

« Tout homme porte sur l'épaule gauche un singe et, sur l'épaule droite, un perroquet. » — Jean Cocteau
« Moi je cherche plus de logique non plus. C'est surement pour cela que j'apprécie les Ataris, ils sont aussi logiques que moi ! » — GT Turbo