J'ai besoin de faire un retour arrière pour résoudre un problème Knapsack. Ceci est un exemple de ce que je pourrais avoir à faire pour mon problème. Ma question est, comment puis-je connaître les limites? Je comprends que la limite pour le nœud racine est de 115 $ parce que c'est la somme de toutes les valeurs. Mais ce que je ne comprends pas, c'est comment le bon enfant de la racine a une limite de 82 $.Retour en arrière pour le sac à dos
Je trouve ce texte expliquant ce que cela signifie, mais je suis encore confus:
For a maximization problem the bound is an upper bound,
– the largest possible solution that can be achieved by
expanding the node is less or equal to the upper bound
Veuillez fournir tous les articles et la limite de poids dont vous parlez. La photo montre 4 objets d'une valeur totale de 40 $ + 30 $ + 50 $ + 10 $ = 130 $. Ce n'est évidemment pas votre 115 $ mentionné. –