Algo de combinaison de modules
Fermé
sam
-
26 oct. 2007 à 14:03
mamiemando Messages postés 33446 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 20 décembre 2024 - 29 oct. 2007 à 09:26
mamiemando Messages postés 33446 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 20 décembre 2024 - 29 oct. 2007 à 09:26
A voir également:
- Algo de combinaison de modules
- Tableau de combinaison loto - Forum Logiciels
- Nombre de combinaison possible avec 10 chiffres ✓ - Forum Programmation
- Combinaison de 5 chiffres allant de 1 à 18 - Forum Mail
- Combien de combinaison possible avec 3 chiffres - Forum Programmation
- Combien de combinaison possible avec 4 chiffres - Forum Programmation
3 réponses
mamiemando
Messages postés
33446
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
20 décembre 2024
7 812
26 oct. 2007 à 16:01
26 oct. 2007 à 16:01
A ta place je regarderais du côté des problèmes de sac à dos.
https://fr.wikipedia.org/wiki/Probl%C3%A8me_du_sac_%C3%A0_dos
Bonne chance
https://fr.wikipedia.org/wiki/Probl%C3%A8me_du_sac_%C3%A0_dos
Bonne chance
Ouaou !!!
ça correspond effectivement à mon problème mais alors ne n'y comprend rien :>
merci en tout cas à mamiemando pour le tuyau !!!
ça correspond effectivement à mon problème mais alors ne n'y comprend rien :>
merci en tout cas à mamiemando pour le tuyau !!!
mamiemando
Messages postés
33446
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
20 décembre 2024
7 812
29 oct. 2007 à 09:26
29 oct. 2007 à 09:26
HUm alors en fait le problème de sac à dos est un problème classique en recherche opérationnelle. Si ma mémoire et bonne il se définit ainsi :
- chaque élément (xi) à une valeur (vi) et un poids (wi)
- le sac à dos ne permet de transporter qu'un certain poids (W)
- on cherche à remplir le sac à dos de sorte à transporter une valeur maximale
Concrètement en recherche opérationnelle, un problème se décrit :
- avec des variables et les ensembles de définition de ces variables (prends-je l'élément i ou pas : xi in {0,1} etc) dans la mesure du possible continue (les variables booléennes et entières rendent le problème plus difficile à résoudre pour un solveur)
- avec des contraintes (poids max : W, poids des éléments : les constantes wi ; le poids du sac : sum(wi.xi) d'où la contrainte sum(wi.xi) <= W) dans la mesure du possible large (<= et >= au lieu de < et >). Il faut dans la mesure du possible avoir des contraintes linéaires (ie de la forme sum(ai.xi) <= K ou ai et K sont des constantes).
- avec un objectif (valeur d'un objet : constantes vi ; objectif : max(sum(vi.xi)))
Une fois le problème modélisé sur le papier, si le problème est "difficile" on utilise un solveur (par exemple coin ou cplex). Or le problème de sac à dos est un problème difficile ! Par problème difficile il faut comprendre qu'on ne connaît pas d'algorithme polynomial pour le résoudre de manière exacte (d'où l'utilisation d'un solveur qui va explorer chaque combinaison d'objet). Quand la résolution est trop longue avec un solveur, on utilise souvent des meta heuristiques qui donnent souvent et très rapidement une solution de bonne qualité (presque optimale).
Pour résumer ce que je viens de te dire :
- retiens que ton problème a été archi traité dans le domaine de la recherche opérationnelle si c'est bien un problème de sac à dos,
- un tel problème peut être résolu avec un solveur (coin ou cplex par exemple) mais si le problème est gros, le temps de calcul peut être très long,
- on peut le résoudre de manière approchée et sans solveur avec des méta heuristique dans un temps très raisonnable et avec une solution de bonne qualité.
Bonne chance
- chaque élément (xi) à une valeur (vi) et un poids (wi)
- le sac à dos ne permet de transporter qu'un certain poids (W)
- on cherche à remplir le sac à dos de sorte à transporter une valeur maximale
Concrètement en recherche opérationnelle, un problème se décrit :
- avec des variables et les ensembles de définition de ces variables (prends-je l'élément i ou pas : xi in {0,1} etc) dans la mesure du possible continue (les variables booléennes et entières rendent le problème plus difficile à résoudre pour un solveur)
- avec des contraintes (poids max : W, poids des éléments : les constantes wi ; le poids du sac : sum(wi.xi) d'où la contrainte sum(wi.xi) <= W) dans la mesure du possible large (<= et >= au lieu de < et >). Il faut dans la mesure du possible avoir des contraintes linéaires (ie de la forme sum(ai.xi) <= K ou ai et K sont des constantes).
- avec un objectif (valeur d'un objet : constantes vi ; objectif : max(sum(vi.xi)))
Une fois le problème modélisé sur le papier, si le problème est "difficile" on utilise un solveur (par exemple coin ou cplex). Or le problème de sac à dos est un problème difficile ! Par problème difficile il faut comprendre qu'on ne connaît pas d'algorithme polynomial pour le résoudre de manière exacte (d'où l'utilisation d'un solveur qui va explorer chaque combinaison d'objet). Quand la résolution est trop longue avec un solveur, on utilise souvent des meta heuristiques qui donnent souvent et très rapidement une solution de bonne qualité (presque optimale).
Pour résumer ce que je viens de te dire :
- retiens que ton problème a été archi traité dans le domaine de la recherche opérationnelle si c'est bien un problème de sac à dos,
- un tel problème peut être résolu avec un solveur (coin ou cplex par exemple) mais si le problème est gros, le temps de calcul peut être très long,
- on peut le résoudre de manière approchée et sans solveur avec des méta heuristique dans un temps très raisonnable et avec une solution de bonne qualité.
Bonne chance