| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Метод ветвей и границ |
| Автор: Goganchic 23.5.2008, 19:54 |
| Всем привет! У меня такой вопрос: не мог бы кто-нибудь объяснить мне метод ветвей и границ, а точнее его применение к задаче о ранце. Т.е. у нас имеется объем ранца, а так же N предметов, для которых задан объем и полезность. Надо выбрать набор предметов таким образом, чтобы получить максимальную полезность и заполнить весь ранец. Мне не очень понятно по какому принципу здесь происходит ветвление. Заранее благодарен за ответ. |
| Автор: maxdiver 23.5.2008, 21:07 |
Ветвление - ну берём или не берём предмет. И так для каждого предмета, разветвление на 2 ветви (хорошо сказал  ).А по поводу отсечений - ну первое, что пришло в голову - если суммарный объём оставшихся вещей меньше того объёма, который нам осталось набрать, то сразу выходим из ветви. И если суммарная эффективность оставшихся вещей <= текущей наилучшей найденной эффективности, то тоже выходим из ветви. |