Discussion :

[lepatantpato]

Bonjour tout le monde

Voici un problème que je sais résoudre par analyse de toutes les combinaisons, mais qui peut prendre beaucoup de temps selon la quantité de données ...
je chercher un algo capable de l'améliorer. Le problème est le suivant:
J'ai 4 produits A B C et D.
J'ai 5 articles 1 2 3 4 et 5, utilisant, avec quantité fournie, 1 ou 2 ou 3 ou 4 produits.
Tous les articles doivent être traités.
Je cherche à utiliser, pour les 5 articles, le moins de produits possibles, sachant que la totalité de chaque produit ne peut dépasser 5.
Exemple :


un bon résultat serait :


Si on regarde les colonnes B et C, toutes les contraintes sont respectées :
- à la fois tous les articles (les lignes) sont traités,
- le total de chaque colonne est <=5
- un minimum de produits (ici 2, B et C) . Donc B et C sont un bon résultat.
Par contre, A C et D sont aussi un résultat, mais avec 3 produits, donc moins intéressant.
Quelqu'un aurait une piste d'algo à m'indiquer (ou à quel type de problème se rattache le mien ) ?
Merci !

[Trap D]

Une bonne solution serait de se tourner vers la programmation par contraintes, en Prolog par exemple mais il existe aussi des bibliothèques en Java

[lepatantpato]

Bonjour
Oui, je connais Prolog, j'ai bien aimé à l'époque (il y a longtemps...).
Mais bon, pour l'instant, peux tu m'en dire plus sur les bibliothèques java ?
cdt

[Trap D]

La aussi ça date un peu, j'ai un peu utilise choco, mais je ne sais pas si c'est maintenu.
Pour en revenir à Prolog, il y a un interface JPL entre Java avec SWI-Prolog qui fonctionne très bien (une fois les problèmes de CLASSPATH résolus).
[EDIT] Ca fonctionne toujours et apparemment ça a pris de l'ampleur : http://www.choco-solver.org/ [/EDIT]

[lepatantpato]

En fait , je cherche un algo pour l'adapter dans mon langage de programmation, ou bien encore une piste de recherche..
Merci !

[anapurna]

salut

en regardant sans trop réfléchir
la première étape serais de trier tes colonne du plus petit nombre d’éléments au plus grand nombre
et du score mini au sore maxi

dans ton exemple on a donc
D (1,1)
C(2,3)
B(3,4)
A(3,5)

ensuite tu vérifie que N ne peut pas appartenir aux groupe supérieur ou dans une colonne Résume qui comporte les élément que l'on sélectionne
donc pour D c'est un cas particulier ce n'est que le cas supérieur
on vois qu'il se trouve dans B on supprime D
on passe a C on vois bien qu'il a un élément qui se trouve nulle part on remplit notre colonne Résume (-,1,-,2,-)
on passe a B pareille que pour C il y a un élément qui n'est pas indiqué (3) puisque l'on supprimé la colonne D
on remplit a nouveau notre colonne Résume (1,1,1,2,2)
on passe a la colonne A tous les éléments se trouvent dans la colonne résume on peut l'effacer

au final il nous reste donc C et D voila