У меня есть проблема, которую нужно решить с помощью алгоритма ветвей и границ, однако мне трудно думать, как ее решить. Я не могу понять, как запустить алгоритм ветвей и границ.
Вот проблема:
Автомобиль имеет максимальный вес и вместимость, и мне нужно заполнить автомобиль пакетами. Эти пакеты имеют определенное значение важности, веса и объема. Цель состоит в том, чтобы поместить в автомобиль комбинацию пакетов с наибольшей ценностью, не выходя за пределы веса и объема автомобиля.
Для ветвей и границ вам нужно знать, как описать частичное решение и как определить, насколько хорошим оно может быть. Частичным решением может быть список пакетов, которые, как вы решили, обязательно войдут в машину, независимо от того, что вы еще добавите. Вы можете вычислить верхнюю границу того, сколько стоимости войдет в автомобиль, посмотрев, сколько места и веса осталось, и среди оставшихся упаковок, какова наибольшая сумма стоимости на единицу объема и стоимость на единицу. вес есть.
