Рюкзак ветка и переплет

Question

Рюкзак ветка и переплет

У меня есть следующие данные:

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

Спасибо уже за вашу помощь.

1

algorithm backtracking knapsack-problem branch-and-bound

Источник

user2398147 11 дек '13 в 14:05

1 ответ

Другие вопросы по тегам algorithm backtracking knapsack-problem branch-and-bound

user3060498 22 янв '14 в 09:14 2014-01-22 09:14 · Answer 1 · 2014-01-22 09:14

Верхняя граница для нулевого узла - это жадное решение дробного ранца. Просто возьмите элемент с наибольшим соотношением цена / вес и продолжайте вставлять его до тех пор, пока не останется свободного места или вы не вставите его полностью. И повторите процесс.