3

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

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. Есть три предмета:

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

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

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

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

В итоге я получу 7, что подтверждает следующая пикча: В квадратных скобках указаны суммарная ценность на данном шаге алгоритма, оптимальное решение помечено. Косая линия говорит о том, что предмет взят, горизонтальная говорит об обратном.

6
  • пожалуйста, покажите фрагменты с данными 29 ноя 2015 в 13:27
  • Не совсем понял, какие именно данные вы хотите увидеть 29 ноя 2015 в 14:00
  • меня интересует фрагмент, где Вы её вызываете. 29 ноя 2015 в 14:06
  • @YuriNegometyanov GetMaxSumAvailability(ItemList, 0, 0, 0); вызывается по кнопке 29 ноя 2015 в 14:22
  • спасибо........ 30 ноя 2015 в 2:25

1 ответ 1

4

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

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

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

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

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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.