Backtracking for Knapsack

Question

Мне нужно использовать backtracking для решения проблемы с рюкзаком. Это пример того, что я мог бы сделать для своей проблемы. Мой вопрос в том, как я знаю границы? Я понимаю, что ограничение для корневого узла составляет $ 115, потому что это сумма всех значений. Но то, что я не понимаю, - это то, как правый ребенок корня имеет размер в 82 доллара.

Я нашел этот текст, объясняющий, что это значит, но я до сих пор путают:

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 

Answer 1

Я понял это:

связан = прибыль + p1 + p2 + (C - 7) * p3/w3 = $ 0 + $ 40 + $ 30 + (16 -7) X $ 50/10 = $ 115