Решение задачи о рюкзаке методом ДП САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ АКАДЕМИКА С. П. КОРОЛЕВА Докладчик: Грязнов А.Г Преподаватель: - презентация

1 Решение задачи о рюкзаке методом ДП САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ АКАДЕМИКА С. П. КОРОЛЕВА Докладчик: Грязнов А.Г Преподаватель: Даниленко А.Н Самара, 2014

2 Введение 1. Мы познакомимся с задачей о ранце. 2. Рассмотрим методы решения задачи о ранце. 3. Изучим сложность каждого из алгоритмов. 4. Рассмотрим метод динамического программирования. 5. Сформулируем прикладную задачу на базе задачи о рюкзаке. 6. Предложим вариант автоматизированного решения сформулированной задачи.

3 Задача о ранце Задача о ранце (рюкзаке) (англ. Knapsack problem) одна из NP задач комбинаторной оптимизации. Название своё получила от максимизационной задачи укладки как можно большего числа ценных вещей в рюкзак при условии, что общий объём (или вес) всех предметов, способных поместиться в рюкзак, ограничен.

4 Варианты задачи Рюкзак 0-1 (англ. 0-1 Knapsack Problem) Ограниченный рюкзак (англ. Bounded Knapsack Problem) Неограниченный рюкзак(англ. Unbounded Knapsack Problem) Рюкзак с мульти выбором (англ. Multiple-choice Knapsack Problem) Мультипликативный рюкзак (англ. Multiple Knapsack Problem) Многомерный рюкзак (англ. Multy-dimensional knapsack problem)

5 Методы решения Точные алгоритмы Полный перебор Метод ветвей и границ Динамическое программирование(алгоритм Беллмана) Приближенные алгоритмы Жадные алгоритмы Метаалгоритмы Генетический алгоритм

6 Сложность алгоритмов Полный перебор. O(2 n )Метод ветвей и границ. O(2 n /sqrt(n))... O(2 n ) Динамическое программирование. O(nW)Жадный алгоритм. O(nlogn)

7 O(NW ) Динамическое программирование Динамическое программирование способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой (англ.), выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений можно значительно сократить. Метод динамического программирования сверху это простое запоминание результатов решения тех подзадач, которые могут повторно встретиться в дальнейшем. Динамическое программирование снизу включает в себя переформулированные сложной задачи в виде рекурсивной последовательности более простых подзадач.

8 Сформулируем задачу В некотором университете есть студент, который делает расчетные и лабораторные работы своим одногруппникам за деньги. Поскольку сессия приближается, время ограничено. Каждая работа требует различных затрат по времени, но и заплатят за каждую по разному. Студенту хочется заработать как можно больше в рамках этого срока. С помощью метода динамического программирования найти решение очень просто.

9 Решение Имя СуммаДни Студенты\Срок Мария Сергей Павел Ольга Марина Евгений Антон Анна

10 C# Основное тело программы c# func = new int[maxWeight + 1, numsArticle]; //Реализуем массив функции //Реализуем алгоритм Беллмана for (weight = 1; weight weight) { func[weight, i] = func[weight, i - 1]; //тогда берем предыдущий набор articles[i].take = false; } else if (func[weight, i - 1] >= (func[weight - articles[i].weight, i - 1] + articles[i].price)) { func[weight, i] = func[weight, i - 1]; //тогда берем предыдущий набор articles[i].take = false; } else { func[weight, i] = func[weight - articles[i].weight, i - 1] + articles[i].price; //иначе добавляем к предыдущему набору текущую работу articles[i].take = true; } Print(); Console.ReadKey();

11 Работа программы

12 Используемые источники %B0%D0%BD%D1%86%D0%B5 %B0%D0%BD%D1%86%D0%B D1%80%D1%8E%D0%BA%D0%B7%D0%B0%D0%BA%D0%B5#.D0.92.D0.B0.D1.80.D0.B8.D0.B0.D0.BD.D1.82. D1.8B_.D1.80.D0.B5.D1.88.D0.B5.D0.BD.D0.B8.D1.8F_2 D1%80%D1%8E%D0%BA%D0%B7%D0%B0%D0%BA%D0%B5#.D0.92.D0.B0.D1.80.D0.B8.D0.B0.D0.BD.D1.82. D1.8B_.D1.80.D0.B5.D1.88.D0.B5.D0.BD.D0.B8.D1.8F_2 ИЗУЧЕНИЕ РАЗЛИЧНЫХ ПОСТАНОВОК ЗАДАЧИ О РЮКЗАКЕ И МЕТОДОВ ИХ РЕШЕНИЯ. Додонова М.М.

13 Спасибо за внимание! До скорых встреч! Самара, 2014 Конец.