Trouver « branche minimum » d'un arbre - solution au problème de l'entrepôt

Question

J'ai un entrepôt où je garde les marchandises. Chaque article occupe un volume donné d'espace d'entrepôt et les coûts donnent la quantité de dollars.

Maintenant, parce que l'entrepôt est plein et j'attends une nouvelle livraison, je dois libérer de l'espace - pas moins que la nouvelle livraison n'occupera, mais je dois aussi minimiser mes pertes. En d'autres termes, je dois vider au moins X mètres cubes d'espace d'entrepôt en jetant quelques articles, en m'assurant que la valeur de ces articles est la valeur minimale possible. Si X = 10m3, alors je préfère jeter un objet qui occupe 20m3 et vaut 1000 $ par rapport à un objet qui occupe exactement 10m3 mais qui vaut 2000 $. Bien sûr, dans le calcul réel, il sera nécessaire de jeter plus d'un objet, probablement 5, 10 ou peut-être même 20.

Ce à quoi je pense est de représenter le problème ci-dessus comme un arbre, avec des nœuds représentant le volume de l'espace vide et des arêtes qui représentent lost value, puis la recherche pour les noeuds qui ont une valeur supérieure ou égale à X, puis en choisissant le noeud qui a le plus bas lost value le long des bords de la racine de l'arbre à ce noeud.

Ce que je ne suis pas sûr que ce soit une bonne approche parce que, pour exemple 100 éléments dans l'arborescence de l'entrepôt complet auraient 100 nœuds au premier niveau de profondeur, 100 * 99 = 9900 nœuds au deuxième niveau, etc., ce qui commence rapidement à être prohibitif.

Y a-t-il une meilleure approche, ou peut-être même un algorithme éprouvé (que je ne connais pas) pour ce genre de problèmes?

Answer 1

Ceci est connu comme le Knapsack problem.

Changer votre problème un peu pour le rendre conforme à la besace: la liste de tous les articles que vous avez dans l'entrepôt + tous les éléments que vous souhaitez ajouter. Rechercher le meilleur rapport qualité-prix. Eh bien, dans ce cas, cela signifie que vous n'essaieriez pas de dégager de l'espace dans votre entrepôt pour des déchets, ce que je ne pense pas être trop stupide.

Ah, si vous ne suivez pas le lien, il NP-complet, vous êtes un mot de mal si vous voulez la meilleure solution :)