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