Решение задачи об упаковке рюкзака и её применение в прикладных задачах

1.

КУБГУ
ФАКУЛЬТЕТ МАТЕМАТИКИ И
КОМПЬЮТЕРНЫХ НАУК
РЕШЕНИЕ ЗАДАЧИ ОБ УПАКОВКЕ РЮКЗАКА И ЕЁ
ПРИМЕНЕНИЕ В ПРИКЛАДНЫХ ЗАДАЧАХ
РАБОТУ ВЫПОЛНИЛ,
СТУДЕНТ 3 КУРС
КАРАПЕТЯН Д.К.
НАУЧНЫЙ РУКОВОДИТЕЛЬ,
ДОЦЕНТ, КАНДИДАТ
ТЕХНИЧЕСКИХ НАУК
ВИШНЯКОВ Р.Ю.
КРАСНОДАР 2021

2.

ПРОБЛЕМАТИКА И АКТУАЛЬНОСТЬ ЗАДАЧИ РЮКЗАКА

3.

ЦЕЛИ, ЗАДАЧИ ДАННОЙ РАБОТЫ
Исследование задачи рюкзака
Практическое применение задачи

4.

ПОСТАНОВКА ЗАДАЧИ
ПОДАЧА ОГРАНИЧЕНИЙ
СПИСОК ПРЕДМЕТОВ И
ОПТИМАЛЬНАЯ ВЫБОРКА
СВЕДЕНИЯ

5.

СУЩЕСТВУЮЩИЕ МЕТОДЫ РЕШЕНИЯ
ПЕРЕБОР
ЭВРИСТИЧЕСКИЕ АЛГОРИТМЫ
ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

6.

ВЫБРАННЫЙ МЕТОД РЕШЕНИЯ
f(k, u) – целевая функция
k – рассматриваемый предмет
u – текущий суммарный вес
Движение функции f(k+1, u + w(k+1))
Рассматриваем (K+1) x (W + 1) состояний

7.

ИНСТРУМЕНТЫ РЕАЛИЗАЦИИ
PyTelegramBotAPI – для подключения к API Telegram
Pandas – для обработки Excel документов

8.

РЕЗУЛЬТАТЫ РАБОТЫ

9.

СПАСИБО ЗА ВНИМАНИЕ!