📄Работа №107420
Тема: Реализация задачи о рюкзаке методом динамического программирования
Тип работы
Бакалаврская работа
Предмет
программирование
Объем:
64 листов
Год:
2017
Просмотров:
250
4780
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
ВВЕДЕНИЕ 3
ГЛАВА 1 ОБЩИЕ ПОДХОДЫ ИСПОЛЬЗОВАНИЯ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ В ПРИКЛАДНЫХ ЗАДАЧАХ 5
1.1 Обоснование необходимости методов динамического
программирования в прикладных задачах 5
1.2 Достаточность методов динамического программирования в
прикладных задачах 8
ГЛАВА 2 КОНКРЕТНЫЕ РЕАЛИЗАЦИИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ В ПРИКЛАДНЫХ ЗАДАЧАХ 15
2.1 Методы динамического программирования в непрерывном случае 15
2.2 Методы динамического программирования в дискретном случае 28
2.2.1 Математическая модель задачи о рюкзаке 28
2.2.2 Методы решения задачи о рюкзаке 30
ГЛАВА 3 ПРОГРАММНАЯ РЕАЛИЗАЦИЯ 38
3.1 Решение задачи о рюкзаке 38
3.2 Описание интерфейса 38
ЗАКЛЮЧЕНИЕ 45
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 46
ПРИЛОЖЕНИЕ
ГЛАВА 1 ОБЩИЕ ПОДХОДЫ ИСПОЛЬЗОВАНИЯ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ В ПРИКЛАДНЫХ ЗАДАЧАХ 5
1.1 Обоснование необходимости методов динамического
программирования в прикладных задачах 5
1.2 Достаточность методов динамического программирования в
прикладных задачах 8
ГЛАВА 2 КОНКРЕТНЫЕ РЕАЛИЗАЦИИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ В ПРИКЛАДНЫХ ЗАДАЧАХ 15
2.1 Методы динамического программирования в непрерывном случае 15
2.2 Методы динамического программирования в дискретном случае 28
2.2.1 Математическая модель задачи о рюкзаке 28
2.2.2 Методы решения задачи о рюкзаке 30
ГЛАВА 3 ПРОГРАММНАЯ РЕАЛИЗАЦИЯ 38
3.1 Решение задачи о рюкзаке 38
3.2 Описание интерфейса 38
ЗАКЛЮЧЕНИЕ 45
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 46
ПРИЛОЖЕНИЕ
📖 Введение
Динамическое программирование в математике и теории вычислительных систем — метод решения задач с оптимальной подструктурой и перекрывающимися подзадачами, который намного эффективнее, чем решение «в лоб». Словосочетание «динамическое программирование» впервые было использовано в 1940-х годах Р. Беллманом для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения задачи, «предшествующей» ей. В 1953 г. он уточнил это определение до современного.
Впервые сформулированная американским математиком Д.Б. Данцигом задача о рюкзаке (ранце) (англ. Knapsack problem) - одна из NP-полных задач комбинаторной оптимизации, популярность которой вызвана большим количеством её приложений, поскольку многие из реально возникающих задач описываются в рамках данной модели. Основные сферы применения находятся в областях планирования и управления производственными и транспортными системами. Название своё получила от максимизационной задачи укладки как можно большего числа ценных вещей в рюкзак при условии, что общий объём (или вес) всех предметов, способных поместиться в рюкзак, ограничен. Непосредственно термин «рюкзак» может быть интерпретирован достаточно широко. Данная задача и её варианты широко используются для моделирования большого числа практических задач.
Актуальность работы заключается в том, что мы можем решить задачу, в которой присутствует оптимальная подструктура, проделывая следующие три шага.
1) Разбиение задачи на подзадачи меньшего размера.
2) Нахождение оптимального решения подзадач рекурсивно, проделывая такой же трехшаговый алгоритм.
3) Использование полученного решения подзадач для
конструирования решения исходной задачи.
Объект исследования - математическая модель задачи о рюкзаке.
Предмет исследования - оптимизация задачи о рюкзаке методом динамического программирования.
Целью выпускной квалификационной работы является использование метода динамического программирования для решения задачи о рюкзаке.
Задачи работы:
1) Изучение общих подходов динамического программирования;
2) Создание алгоритма для решения задачи о рюкзаке;
3) Программная реализация задачи о рюкзаке.
Выпускная квалификационная работа состоит из введения, трёх глав, заключения, списка используемых источников.
В главе 1 рассматриваются общие подходы использования динамического программирования в прикладных задачах. В главе 2 приводятся конкретные реализации динамического программирования в прикладных задачах. В главе 3 разрабатываются алгоритм и интерфейс программы. В заключении представлены результаты и выводы о выполненной работе.
Впервые сформулированная американским математиком Д.Б. Данцигом задача о рюкзаке (ранце) (англ. Knapsack problem) - одна из NP-полных задач комбинаторной оптимизации, популярность которой вызвана большим количеством её приложений, поскольку многие из реально возникающих задач описываются в рамках данной модели. Основные сферы применения находятся в областях планирования и управления производственными и транспортными системами. Название своё получила от максимизационной задачи укладки как можно большего числа ценных вещей в рюкзак при условии, что общий объём (или вес) всех предметов, способных поместиться в рюкзак, ограничен. Непосредственно термин «рюкзак» может быть интерпретирован достаточно широко. Данная задача и её варианты широко используются для моделирования большого числа практических задач.
Актуальность работы заключается в том, что мы можем решить задачу, в которой присутствует оптимальная подструктура, проделывая следующие три шага.
1) Разбиение задачи на подзадачи меньшего размера.
2) Нахождение оптимального решения подзадач рекурсивно, проделывая такой же трехшаговый алгоритм.
3) Использование полученного решения подзадач для
конструирования решения исходной задачи.
Объект исследования - математическая модель задачи о рюкзаке.
Предмет исследования - оптимизация задачи о рюкзаке методом динамического программирования.
Целью выпускной квалификационной работы является использование метода динамического программирования для решения задачи о рюкзаке.
Задачи работы:
1) Изучение общих подходов динамического программирования;
2) Создание алгоритма для решения задачи о рюкзаке;
3) Программная реализация задачи о рюкзаке.
Выпускная квалификационная работа состоит из введения, трёх глав, заключения, списка используемых источников.
В главе 1 рассматриваются общие подходы использования динамического программирования в прикладных задачах. В главе 2 приводятся конкретные реализации динамического программирования в прикладных задачах. В главе 3 разрабатываются алгоритм и интерфейс программы. В заключении представлены результаты и выводы о выполненной работе.
✅ Заключение
В выпускной квалификационной работе представлены общие подходы необходимости использования динамического программирования в некоторых прикладных задачах.
В настоящее время разработаны современные методы и алгоритмы решения задач дискретной оптимизации. Применение пакетов программ возможно без знания алгоритмов решения задач, однако знание алгоритмов и технологий их реализации позволяет более эффективно использовать прикладные программы. В этих программах используются алгоритмы, связанные с перебором большого числа вариантов, комбинаторные алгоритмы.
В работе подробно рассмотрены реализации динамического программирования в дискретном случае, а так же упомянуты реализации динамического программирования в непрерывном случае. Работа посвящена задаче о рюкзаке, методам её решения. Из них рассмотрены: метод ветвей и границ и метод динамического программирования. Программная реализация осуществлена для метода динамического программирования.
Задача о рюкзаке является довольно удачным примером демонстрации комбинаторных методов поиска оптимального решения метода динамического программирования.
Предложенная модификация алгоритма Беллмана-Форда,
использованная в программе для решения задачи о рюкзаке, в отличии от существующих программ, позволяет проводить расчеты в несколько раз быстрее, исключая ненужные операции.
В настоящее время разработаны современные методы и алгоритмы решения задач дискретной оптимизации. Применение пакетов программ возможно без знания алгоритмов решения задач, однако знание алгоритмов и технологий их реализации позволяет более эффективно использовать прикладные программы. В этих программах используются алгоритмы, связанные с перебором большого числа вариантов, комбинаторные алгоритмы.
В работе подробно рассмотрены реализации динамического программирования в дискретном случае, а так же упомянуты реализации динамического программирования в непрерывном случае. Работа посвящена задаче о рюкзаке, методам её решения. Из них рассмотрены: метод ветвей и границ и метод динамического программирования. Программная реализация осуществлена для метода динамического программирования.
Задача о рюкзаке является довольно удачным примером демонстрации комбинаторных методов поиска оптимального решения метода динамического программирования.
Предложенная модификация алгоритма Беллмана-Форда,
использованная в программе для решения задачи о рюкзаке, в отличии от существующих программ, позволяет проводить расчеты в несколько раз быстрее, исключая ненужные операции.
ИЛИ
Поиск аналога
📕 Список литературы
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.