Решение задач о рюкзаке методом ветвей и границ

#c_sharp #алгоритм #математика

Пытаюсь реализовать решение задач о рюкзаке методом ветвей и границ. По условию вместительность
рюкзака ограничена, а предметы можно положить только один раз. Нужно получить максимальную
суммарную полезность. Вот код метода, который ее вычисляет:

void GetMaxSumAvailability(List ItemList, int i, int currentWeight, int currentCost)
{
    if(i <= ItemList.Count - 1)
    {
        // Если по весу проходит, то прибавляем стоимость и суммарный вес 
        if (currentWeight + ItemList[i].Weight <= width)      
        {
            ItemList[i].Use = true;
            GetMaxSumAvailability(ItemList, i + 1, currentWeight + ItemList[i].Weight,
currentCost + ItemList[i].Availability);
        }
        // Иначе не берем и смотрим следующий элемент
        else
        {
            ItemList[i].Use = false;
            GetMaxSumAvailability(ItemList, i + 1, currentWeight, currentCost);
        }
    }
    if (maxCost < currentCost && width >= currentWeight)
    {
        ItemList.ForEach(delegate(Item item) { if (item.Use) maxCost += item.Availability; });
        GetMaxSumAvailability(ItemList, i + 1, currentWeight, currentCost);
    }
}


Проблема заключается в неправильном выводе. К примеру, пусть width (вместительность
рюкзака) = 5. Есть три предмета:


Вес = 4; Ценность = 100
Вес = 2; Ценность = 60
Вес = 2; Ценность = 60


Тогда на выводе я получу 100, когда очевидно, что если взять 2 и 3 предмет, то суммарная
стоимость будет 120.

Однако, следующий пример выполняется правильно:
widht = 14


Вес = 5; Ценность = 3
Вес = 10; Ценность = 5
Вес = 6; Ценность = 3
Вес = 5; Ценность = 2


В итоге я получу 7, что подтверждает следующая пикча:

    

Ответы

Ответ 1

Уберите  GetMaxSumAvailability в else - не надо подменять накопленные параметры текущими.
Оставьте только ItemList[i++].Use = false; Увы, не всё так просто.

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

Если говорить о графике, то горизонтальная линия при подобном подходе отсутствует,
а ограничения лишь маскируют этот факт. Чтобы эта линия возникала, надо рассматривать
вариант с false даже в том случае, когда предмет влезает. Потому что в приведённом
виде алгоритм не проверяет, что могло бы оказаться в рюкзаке вместо текущего предмета.
И, таким образом, не рассматривает все варианты.

В конечном итоге, все стратегии перебора ведут к одним и тем же допустимым наборам.
Единственная внятная оптимизация состоит в той же "жадной" стратегии, позволяющей быстрее
набить рюкзак и тем самым - отсечь недопустимые варианты.
Метод ветвей и границ в данном случае ведёт только к тому, что рюкзак с вещами будет
объявлен вершиной графа, а процесс набивания рюкзака - движением по его рёбрам.

Итак, рекомендаций две:
1. Упорядочить предметы по весу и начинать перебор с более тяжёлых (жадная стратегия).
2. Рассматривать вариант ItemList.Use = false даже и в том случае, когда предмет
влазит в рюкзак. Поскольку рекурсия в конце концов приведёт к оценке, то достаточно
просто сравнивать эти два варианта при их наличии (бинарный перебор).