Bonjour,
Après avoir passé plusieurs jours sur ce problème (sans succès :'( ), je viens vous poser la question :
Etant donnés n pierres précieuses (v,b) (de valeur v et se trouvant dans une boite b), comment les répartir en m lots de valeur totale V.
Certaines pierres sont des diamants, il ne peut y avoir qu'un diamant par lot au maximum. Une contrainte supplémentaire est que le nombre de boite d'origine d'un même lot doit rester inférieur à B.
J'ai commencé en rangeant les pierres dans un ordre décroissant de valeur, et en les répartissant dans les lots en respectant les différentes contraintes.
Résultat : on obtient des lots incomplets
J'ai ensuite essayé en donnant les diamant, puis en remplissant chaque lot un par un, pour un même résultat.
En fouillant sur le net, j'ai remarqué que ce problème ressemble au problème du sac à dos, et qu'une programmation dynamique permettrait de le résoudre en temps pseudo-polynomial.
Le hic, c'est que je n'y connais pas grand chose en programmation dynamique et que je ne sais pas par où commencer
Merci d'avance pour votre aide,
--
Syl
Partager