Лабораторная_работа_№6_6203_НизамоваДР

1. Лабораторная работа №6

Л А Б О Р А Т О Р Н А Я
Р А Б О Т А
№ 6
Кошачий
рейд
ДИНАМИЧЕСКОЕ
Лабораторную работу №6
По алгоритмам и анализу сложности
Выполнила студентка группы 6203-020302D
Низамова Диана Руслановна
ПРОГРАММИРОВАНИЕ

2. Знакомство

ЗНАКОМСТВО
ЗДРАВСТВУЙТЕ! МЕНЯ ЗОВУТ
МИШКА, И Я КОШЕЧКА
ПРОФЕССОР УСАТЫХ НАУК! БУДУ
РАДА ОБЪЯСНИТЬ ВАМ ЗАДАЧКИ!
ДОБРЫЙ МЯУ, МЕНЯ ЗОВУТ
ТИМА, И Я КОТИК МАГИСТР
ОТДЫХА!
НО РАДИ ВАС ГОТОВ
ПОУЧАСТВОВАТЬ
И РАЗБАВИТЬ ЭТИ ЗАДАЧКИ
СВОИМ ФИРМЕННЫМ СТИЛЕМ!

3. Задача №1

ЗАДАЧА №1
ЭКСКЛЮЗИВНЫЙ
РЕЙД
ОТ МИШКИ!

4. Таблица предметов

Тима, отвлекись от своего расслабона!
У нас серьезная задача! Ночью мы
штурмуем кухонную тумбочку.
Наша общая грузоподъемность — 8 кг.
На полке лежат четыре уникальные
вещи, каждая в единственном
экземпляре. Нужно выбрать самый
ценный набор. Повторять предметы
нельзя!
Погоди, а почему нельзя просто
взять три лежанки? Я бы весь
день на них отдыхал…
Потому что лежанка ОДНА, Тима! Либо
мы её берем – 1 , либо оставляем - 0.
Смотри на таблицу ресурсов:
А-а-а, догнал! То есть если я заберу
мышь и лежанку, они займут ровно 8
кг, а ценность будет 14. И больше
таких вещей нет. Жаль, конечно...
ТАБЛИЦА
ПРЕДМЕТОВ
Предмет
Вес
Ценность
Пакетик
корма
2
4
Игрушечная
мышь
3
5
Кошачья
мята
4
7
Лежанка
5
9

5. Мишка поясняет Задачу Математическим языком

МИШКА ПОЯСНЯЕТ ЗАДАЧУ
МАТЕМАТИЧЕСКИМ ЯЗЫКОМ
Рекуррентное соотношения для рюкзака:
A[w, i] = max{A[w − wᵢ, i−1] + cᵢ,
Тима, запомни! i — это номер
предмета, а w — текущий вес. Мы либо
берем уникальный предмет, либо
используем результат без него.
Третьего не дано!
A[w, i−1]}

6. Матрица пересчета

МАТРИЦА ПЕРЕСЧЕТА
w\i
0
1(Корм)
2(Мышь)
3(Мята)
4(Лежанк
а)
0
0
0
0
0
0
2
0
4
4
4
4
4
0
4
4
7
7
5
0
4
9
9
9
8
0
4
9
11
14
Результат Миши равен 14, если она возьмет лежанку и мышь.

7. Задача №2

ЗАДАЧА №2
БЕЗЛИМИТНЫЙ
ШОППИНГ
ОТ ТИМЫ!

8. Таблица предметов

Мишка, смотри! Я нашел нижний ящик, а
там — оптовый склад! Тут целые
коробки одинаковых ништяков. Веса и
ценность те же, но брать можно
сколько угодно раз! Мои 8 кг
грузоподъемности наконец-то
разгуляются!
О, а вот это уже задача
неограниченного рюкзака. И
какую же стратегию выберет наш
магистр отдыха?
Ну, раз ограничений на уникальность
нет, я просто возьму 4 пакетика
корма! Каждая весит по 2 кг, как раз
забью все 8 кг веса. А суммарная
ценность выйдет 16 — это даже больше,
чем в твоем плане!
Хвалю, Тима! Математически это
действительно самый оптимальный выбор.
Динамическое программирование работает
безупречно.
ТАБЛИЦА
ПРЕДМЕТОВ
Предмет
Вес
Ценность
Пакетик
корма
2
4
Игрушечная
мышь
3
5
Кошачья
мята
4
7
Лежанка
5
9

9. Тима поясняет Задачу Математическим языком

ТИМА ПОЯСНЯЕТ ЗАДАЧУ
МАТЕМАТИЧЕСКИМ ЯЗЫКОМ
Рекуррентное соотношения для неограниченного рюкзака:
A[w] = max{ A[w − wᵢ] + cᵢ } для всех wᵢ ≤ w
Мишка, смотри как просто! Нам не нужно
помнить всё прошлое, достаточно знать лучший
результат для меньшего веса. И если корм
вкусный — я возьму его хоть четырежды!

10. Матрица пересчета

МАТРИЦА ПЕРЕСЧЕТА
w
0
1
2
3
4
5
6
7
8
A[w]
0
0
4
5
8
9
12
13
16
Ключевой шаг: A[8] = A[8-2] + 4 = A[6] + 4 = 12 + 4 = 16.
Результат Тимы будет 16, если он возьмет 4 пакетика корма.

11. Сравнение результатов

СРАВНЕНИЕ РЕЗУЛЬТАТОВ
Тима
Мишка
13
13,5
14
14,5
Максимум
15
15,5
16
16,5
Результат
Сложность O(n*W)
Вывод
Оба алгоритма эффективны. Для
Тимы нужно меньше памяти, так
как используется одномерный
массив.
Возможность повторений
увеличивает общую ценность за
счет выбора наиболее
эффективных единиц.

12. Программная реализация

ПРОГРАММНАЯ РЕАЛИЗАЦИЯ
#Тима
dp = [0] * (W + 1)
for w in range(1, W + 1):
for weight, value in items:
if weight <= w:
dp[w] = max(dp[w], dp[w - weight] + value)
#Мишка
dp_table = [[0] * (W + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
for w in range(1, W + 1):
if items[i-1].w <= w:
dp_table[i][w] = max(dp_table[i-1][w],
dp_table[i-1][w - items[i1].w] + items[i-1].v)

13. Спасибо за внимание!

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