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

Пытаюсь реализовать решение задач о рюкзаке методом ветвей и границ. По условию вместительность рюкзака ограничена, а предметы можно положить только один раз. Нужно получить максимальную суммарную полезность. Вот код метода, который ее вычисляет:
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, что подтверждает следующая пикча:

Ответ

Уберите GetMaxSumAvailability в else - не надо подменять накопленные параметры текущими. Оставьте только ItemList[i++].Use = false; Увы, не всё так просто.
В подобного рода задачах есть "жадная" стратегия, когда захватываются сначала более ценные предметы. Но данная реализация - точно не такая, поскольку набивает рюкзак первым, что туда может влезть. И обе эти реализации грешат отсутствием какого бы то ни было перебора.
Если говорить о графике, то горизонтальная линия при подобном подходе отсутствует, а ограничения лишь маскируют этот факт. Чтобы эта линия возникала, надо рассматривать вариант с false даже в том случае, когда предмет влезает. Потому что в приведённом виде алгоритм не проверяет, что могло бы оказаться в рюкзаке вместо текущего предмета. И, таким образом, не рассматривает все варианты.
В конечном итоге, все стратегии перебора ведут к одним и тем же допустимым наборам. Единственная внятная оптимизация состоит в той же "жадной" стратегии, позволяющей быстрее набить рюкзак и тем самым - отсечь недопустимые варианты. Метод ветвей и границ в данном случае ведёт только к тому, что рюкзак с вещами будет объявлен вершиной графа, а процесс набивания рюкзака - движением по его рёбрам.
Итак, рекомендаций две: 1. Упорядочить предметы по весу и начинать перебор с более тяжёлых (жадная стратегия). 2. Рассматривать вариант ItemList.Use = false даже и в том случае, когда предмет влазит в рюкзак. Поскольку рекурсия в конце концов приведёт к оценке, то достаточно просто сравнивать эти два варианта при их наличии (бинарный перебор).