algorithme pour trouver la meilleure combinaison
Supposer que j'ai une liste de 100 produits, chacun a un prix. Chacun dispose également d'une énergie (kJ) de mesure.
Serait-il possible de trouver la meilleure combinaison de 15 produits pour moins de 10$, dont la somme de l'énergie (kJ) était le plus grand, à l'aide de la programmation?
Je sais C#, mais toute langue est fine. Des acclamations.
Mise à jour: d'Avoir un peu de troble de trouver des exemples de code source pour le problème de sac-à-dos. Quelqu'un a une ou sait où en trouver. Été googler pour quelques heures et la nécessité d'obtenir cette triés par demain si possible. Ta.
source d'informationauteur Schotime | 2009-03-25
Vous devez vous connecter pour publier un commentaire.
http://en.wikipedia.org/wiki/Knapsack_problem
Cela sonne plus comme un la programmation linéaire problème.
Découvrez la Méthode Du Simplexe.
Ce est un Entier de Programmation Linéaire, optimisation d'une équation linéaire soumis à des contraintes linéaires, où toutes les variables et les coefficients sont des nombres entiers.
Vous voulez variables includeItem1, ..., includeItemN avec les contraintes 0 ≤ includeItemje ≤ 1 pour toutes les valeurs de jeet includeItem1 + ... + includeItemN ≤ 15, et includeItem1*priceItem1 + ... ≤ 10, la maximisation de includeItem1*kilojouleItem1 + ....
Le coller dans votre logiciel préféré linéaire en nombres entiers solveur et obtenir la solution 🙂
Voir aussi http://en.wikipedia.org/wiki/Linear_programming
Ça n'a pas de sens de dire que votre problème est NP-complet, mais c'est une instance d'un problème NP-complet (genre de problème, donc il ne peut pas être un théoriquement moyen rapide de le faire. Selon l'optimalité que vous souhaitez obtenir et à quelle vitesse ILP solveurs de travail, il pourrait être réalisable dans la pratique.
Je ne pense pas que votre problème est un cas particulier de PAI qui le rend particulièrement facile à résoudre. À la voir comme un sac-à-dos-comme problème, vous pouvez vous limiter à regarder tous les sous-ensembles de 1..100 qui ont tout au plus (ou exactement) 15 éléments, ce qui est polynomial en n---n-choisissez-15, ce qui est inférieur à (n^15)/(15!), mais ce n'est pas très utile lorsque n = 100.
Si vous souhaitez des recommandations pour le solveur de programmes, j'ai essayé de glpk et il trouve agréable à utiliser. Dans le cas où vous voulez quelque chose qui coûte de l'argent, mon maître de conférences toujours parlé de CPLEX comme un exemple.
Qui sonne un peu comme le problème de sac-à-dos. Il existe différentes approches (ordre décroissant par la densité d'énergie, par exemple).
C'est le problème de sac-à-dos si vous pouvez choisir un produit ou pas. Si vous pouvez choisir des valeurs fractionnaires de produits, alors vous pourriez résoudre ce avec la méthode du simplexe, mais la fraction de sac à dos problème a une solution simple.
Commander des produits par l'énergie/prix imbattable, la cueillette de 100% de la plus haute jusqu'à ce que vous manquez d'argent, puis choisissez l'une fraction de la valeur de la plus haute reste.
Par exemple, si les prix sont 4,3,5,4 et les énergies sont 3,5,2,7 la commande est
7/4, 5/3, 3/4, 2/5
Donc, vous choisissez les articles 4 et 2, qui serait au prix de 7$, 3$ restants vous acheter 75% de la première pièce pour un prix de 3 $et une énergie de 3*.75 = 2.25
Cela donnerait un total de l'énergie de 14,25
Note qu'en permettant à des valeurs fractionnaires vous donnera l'objectif supérieur de la valeur que seulement en permettant à 0% ou de 100%, donc pas de solution entière va faire mieux que 14.25 (ou 14 pour cette question étant donné que l'objectif de valeur doit être un entier).
Pour résoudre l'original à dos de problème, vous pouvez utiliser un branch-and-bound qui devrait très bien fonctionner dans la pratique. Supposons que vous disposez d'un candidat de la solution avec un objectif de valeur de z*
Notez que lorsque vous créez le subproblem où vous devez choisir un article, il suffit de soustraire son prix sur le budget et pour ajouter de la valeur au profit, maintenant vous avez un petit problème à résoudre.
Pour une description plus détaillée de regarder Branch and Bound sur Wikipédia.
De la Stony Brook Algorithme de Dépôt des listes de des implémentations pour le problème de sac-à-dos.
Leur livre La Conception D'Un Algorithme Manuel a ce genre d'information pour une grande variété de problèmes.
Oui, comme tout le monde l'a souligné la complexité du problème de sac-à-dos. Quelque chose d'aussi simple peut-être assez bon mais...
Cela me rappelle de la célèbre sac à dos de l'algorithme de
Il devrait être possible de résoudre le problème avec Crème pour Java. Il y a aussi une version de C# disponible CSharpCream.