Discussion :

[kohoji]

Bonjour à tous,

Tout d'abord merci à tout ceux qui pourront m'aider et me conseiller.

J'ai un fichier dont voici le contenue :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
fee	day
130	9
150	12
190	20
190	23
230	27
290	33
330	31
70	9
330	30
110	9
90	6
310	34
330	34
190	22
230	25
170	13

Je dois concevoir un programme me permettant de trouver la plus grande somme de charge
pour un total de 100 jours maximum.

Y-a t-il un algorithme sur lequel je peux me baser ?

[dourouc05]

À ma connaissance, pas d'algorithme prévu pour ça ; par contre, ça semble être un bon cas d'utilisation de la programmation dynamique : déterminer la plus grande somme pour au plus n jours en utilisant les m premières entrées de ta liste ; écrire une équation pour m+1 et n+1 en fonction des résultats déjà calculés.

[kohoji]

Ok, je regarde ça de plus prêt et j'essaye de faire un petit quelque chose avec que
je posterai ici même.

Merci.

EDIT : Je pense que ça s'en rapproche http://fr.wikipedia.org/wiki/Probl%C...sac_%C3%A0_dos

[anapurna]

salut

alors sans trop réfléchir j'aurais dis que dans un premier temps
je ferais le ratio fee / day
dans un deuxième temps je ferais le trie sur ce ratio et enfin
j'essaierais d'obtenir mes 100 jours en prenant de préférence le ratio le plus élevé

voilà ci cela peut te mettre sur la voie

[kohoji]

ça marche !

Je prend note est je travaille dessus.

Merci

[kolodz]

Cela ressemble de très près au problème du sac à dos :
http://fr.wikipedia.org/wiki/Probl%C...sac_%C3%A0_dos

L'idée de ce problème est :
Pour un sac à dos limité en poids, comment optimiser les objets choisit pour prendre le plus de valeur possible.
Sachant que chaque objet à un poids et une valeur.

Si on transpose ton problème :
day = poids
fee = valeur

On a exactement le même problème :
- Comment avoir le plus de "fee" ou X "day" de capacité ?

C'est un problème NP complet. Donc pas d'algorithmes super rapide et optimal. Mais, il existe déjà des algorithmes "simpliste" qui propose des solutions "approchantes".

Cordialement,
Patrick Kolodziejczyk.