4. Сравнительный анализ методов

   1. Динамическое программирование (ДП–алгоритм)

Недостатки:

• Веса предметов целые, если брать вещественные значения, ДП - алгоритм неприменим;

• Для больших значений N количества предметов ДП–алгоритм работает O().

Достоинства:

• Высокая скорость работы по сравнению с другими алгоритмами (для не больших значений N<50);

• Получаем точное решение;

• Имеем оптимальные загрузки рюкзака для всех его весов от 1 до MaxW.

2. Полный перебор

Недостатки:

• Входные данные не велики, т.к. с их увеличением растет и время выполнения;

• Временная сложность O(N!).

Достоинства:

• Полный перебор дает точное решение;

• Простота реализации.

3. Метод ветвей и границ

Недостатки:

• В худшем случае работает как полный перебор.

Достоинства:

• Возможно значительное сокращение времени работы;

• Простота реализации.

4. Жадный алгоритм

Недостатки:

• Всегда можно предоставить такой набор, при котором решение будет не точным.

Достоинства:

• Высокое время работы, ограниченное только скоростью сортировки, в среднем O(NlogN);

• Может работать с большими значениями N;

• Не использует дополнительных ресурсов компьютера;

• Простота реализации.

5. Пример решения задачи с помощью пакета экономических расчетов (ПЭР)

Для демонстрации наличия работоспособного программного обеспечения, направленного на решение задач по дисциплине, в том числе и упомянутой задачи о рюкзаке, рассмотрим решение с помощью программного продукта «ПЭР» – пакета экономических расчетов. Для примера возьмем условия задачи из пункта «3 Динамическое программирование (ДП–алгоритм)», а именно:

• вместимость рюкзака = 5;

• количество предметов = 3:

1. W₁ = 1, P₁ = 6;

2. W₂ = 3, P₂ = 12;

3. W₃ = 2, P₃ = 10.

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

рисунок 4.1

Затем мы конкретизируем задачу:

рисунок 4.2

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

рисунок 4.3

После ввода задачи, т.к. входные данные, откровенно говоря, небольшие, ее решение происходит, практически мгновенно. Пользователю остается лишь выбрать раздел №5 «Решение задачи»:

рисунок 4.4

И в этом разделе посмотреть весь ход решения, либо перейти к итоговой таблице с конечным результатом:

рисунок 4.5

Вот как она (таблица с конечным результатом) выглядит для нашей задачи (как видим, ответ сошелся с ответом, показанным в разделе «3 Динамическое программирование (ДП–алгоритм)»)

рисунок 4.6

6. Модификации задачи

Кроме классической постановки задачи существуют и ее модификации. Для ознакомления приведу примеры некоторых из них:

1. Необходимо вывести только максимальную стоимость, набор нас не интересует.

2. В результате работы нужно получить не только максимальную стоимость, но и сам набор.

3. На размер рюкзака несколько ограничений (многомерность задачи).

4. Каждый предмет можно брать только лишь один раз.

5. Предметы можно брать произвольное количество раз.

6. Количество раз помещения предмета в рюкзак фиксировано. Либо для каждого предмета свое, либо для всех предметов одно.

7. Некоторые предметы должны обязательно быть уложены в рюкзак (имеют приоритет).

8. Находить несколько оптимальных решений (одинаковой стоимости, но с разным содержимым).