1 votes

De quel type d'algorithme s'agit-il ?

Je n'y connais rien, mais voici ce que j'essaie de faire en code... J'ai une classe 'Item', des propriétés int A y int B -- J'ai plusieurs listes de List<Item> avec une quantité aléatoire de Item dans chaque liste, incohérente avec toute autre liste. Je dois choisir 1 élément dans chaque liste pour obtenir la valeur la plus élevée possible de la somme. Item.A tout en se conformant au fait que la somme de Item.B doit également être au minimum d'un certain nombre. À l'avenir, il pourrait y avoir une autre propriété Item.C pour se conformer à cela, la somme doit être égale à un certain nombre. Je n'ai aucune idée de comment écrire cela :(

En d'autres termes, il s'agit de

class Item
  int A
  int B
  int C

Je dispose d'une List<Item> chacun avec un nombre aléatoire de points à l'intérieur

Nous devons trouver la meilleure combinaison possible pour avoir

a) Highest sum of Item.A
b) Constraint that the sum of Item.B must be higher than X
c) Constraint that the sum of Item.C must be equal to X

Je n'ai aucune idée de comment coder cela pour être rapide et efficace :(

3voto

stephan Points 6006

Comme mentionné dans mon commentaire, il s'agit d'un problème de programmation binaire, qui peut être interprété comme un problème de problème de Knapsack multidimensionnel . Je commencerais par essayer de le résoudre à l'aide d'un programme de programmation mixte en nombres entiers (MIP), comme celui suggéré par Lieven dans l'un de ses commentaires ( lpSolve ), étant donné que vous n'avez "que" 100 à 200 variables binaires. Il se peut que vous deviez jouer un peu avec les paramètres. Certains solveurs MIP permettent d'ajouter des heuristiques de recherche, ce qui peut être utile. Compte tenu de vos contraintes, je dois admettre que je n'ai pas d'idée sur le temps que prendra un solveur MIP standard, mais je ne retiendrais pas mon souffle.

Si un solveur de programmation en nombres entiers mixtes n'est pas assez rapide pour vous, vous devez vous tourner vers des algorithmes plus spécialisés. Pour votre problème, ceux présentés dans Problèmes de Knapsack , le chapitre 11.10 sur le problème de Knapsack à choix multiple (presque exactement votre problème) et le chapitre 9 sont pertinents.

Edita: D'après vos commentaires, la bonne nouvelle est que vos plages de données sont assez bonnes et que le problème semble pouvoir être résolu dans un délai raisonnable. Le problème semble pouvoir être résolu dans un délai raisonnable. papier présente un algorithme qui, selon les auteurs, résout les problèmes de votre taille en quelques secondes (voir les sections 4.4 et 5.1). La mauvaise nouvelle est qu'il contient beaucoup de mathématiques...

1voto

ShaunO Points 73

J'ai posté cette question en tant qu'utilisateur non enregistré et après avoir cliqué sur enregistrer, il n'a pas associé mon utilisateur non enregistré à mon utilisateur enregistré, sympa =/

En ce qui concerne le commentaire de van :

En général, il y a environ 14 listes. Dans chaque liste, il y a généralement entre 5 et 15 "éléments". Chaque élément possède ces trois propriétés. Nous doit exactement 1 élément de chaque liste. Nous recherchons la valeur maximale de PropertyA lorsque nous calculons la somme de tous les PropertyA après avoir choisi un élément dans chaque liste. Les contraintes sont les propriétés B et C que la combinaison choisie doit également confirmer, une fois encore en utilisant la somme des valeurs de la combinaison.

Il doit également s'agir de la solution la plus optimale, et non d'une approximation.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X