У меня есть следующие данные:
item weight value value/weight
1 5 40 8
2 2 10 5
3 6 30 5
4 1 12 12
5 2 18 9
Емкость равна 10. Как продолжить расчет верхней границы для узла 0? Я вычисляю верхнюю границу для узла 0 следующим образом:
ub = v + [W-w] * [v/w]
ub = 0 + [10] * [8] = 80
Или мне нужно отсортировать предметы в порядке убывания их стоимости/веса как 12,9,8,5,5? а затем вычислить верхнюю границу? Или я правильно делаю, без сортировки, вычисления верхней границы и перехода к следующему пункту?
В методе без сортировки я не получу максимальную верхнюю границу в узле 0, я так думаю.
ub = 0 + [10] * [12] = 120 // if sorted
Спасибо уже за вашу помощь.
