Un algorithme d'emballage & # 8230; genre de

Question

Étant donné un tableau d'éléments, chacun ayant une valeur et un coût , quel est le meilleur algorithme pour déterminer les éléments requis pour atteindre une valeur minimale coût minimum? , par exemple:

Item: Value -> Cost
-------------------
A     20   -> 11
B     7    -> 5
C     1    -> 2

MinValue = 30
naive solution: A + B + C + C + C. Value: 30, Cost 22
best option: A + B + B.            Value: 34, Cost 21

Notez que le rapport valeur / coût global à la fin n’est pas pertinent ( A + A vous donnerait le meilleur rapport qualité-prix, mais A + B + B est une option moins chère qui atteint la valeur minimale).

Answer 1

C’est le problème du sac à dos. (C'est-à-dire que la version de décision de ce problème est identique à la version de décision du problème de sac à dos, bien que la version d'optimisation du problème de sac à dos soit généralement énoncée différemment.) Il s'agit de NP-hard (ce qui signifie qu'aucun algorithme n'est connu, c'est-à-dire polynôme dans la "taille" - nombre de bits - dans l'entrée). Mais si vos chiffres sont petits (la plus grande "valeur" de l'entrée, par exemple, les coûts importent peu), il existe une solution de programmation dynamique simple.

Laissez best [v] le coût minimum pour obtenir une valeur de (exactement) v. Ensuite, vous pouvez calculer les valeurs mieux [] pour tout v, en (initialisant tous les meilleurs [v] à l'infini et):

best[0] = 0
best[v] = min_(items i){cost[i] + best[v-value[i]]}

Ensuite, recherchez au mieux [v] les valeurs jusqu'au minimum souhaité plus la plus grande valeur; le plus petit d'entre eux vous en donnera le coût.

Si vous voulez les éléments réels (et pas seulement le coût minimum), vous pouvez soit conserver des données supplémentaires, soit simplement consulter le tableau des meilleurs [] s et en déduire.

Answer 2

Ce problème est connu sous le nom de programmation linéaire en nombres entiers. C'est NP-difficile. Cependant, pour les petits problèmes comme votre exemple, il est simple de créer quelques lignes de code afin de forcer toutes les combinaisons de choix d’achat.

NP-harddoes ne signifie pas impossible ou même coûteux, cela signifie que votre problème devient rapidement plus lent à résoudre avec des problèmes à plus grande échelle. Dans votre cas, avec seulement trois points, vous pouvez résoudre ce problème en quelques microsecondes.

Pour la question exacte de savoir quel est le meilleur algorithme en général, il contient des manuels entiers. le bon vieux Wikipedia est un bon début.

Answer 3

Modifier Cette réponse est rédigée car factuellement incorrecte. En suivant les conseils, cela ne vous causera que du tort.

Ce n'est pas vraiment le problème du sac à dos, car il suppose que vous ne pouvez pas emballer plus d'articles que l'espace disponible dans certains conteneurs. Dans ce cas, vous voulez trouver la combinaison la moins chère qui remplira l’espace, en tenant compte du risque de débordement.

Ma solution, que je ne connais pas optimale, mais qui devrait être assez proche, consisterait à calculer pour chaque article le rapport coût / bénéfice, à trouver l’article présentant le plus grand bénéfice / coût et à remplir la structure avec cet article jusqu’à il n'y a pas de place pour un autre article. Ensuite, je testerais pour voir s’il existait une combinaison avec l’un des autres éléments disponibles pouvant occuper l’emplacement disponible à un coût inférieur au coût de l’un des articles les moins chers, puis, si une telle solution existe, utilisez cette combinaison, sinon utilisez-en un de plus. des articles les moins chers.

Amenddum Cela peut également être NP-complet, mais je ne suis pas encore sûr. Quoi qu’il en soit, à toutes fins pratiques, cette variation devrait être beaucoup plus rapide que la solution naïve.