- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Задача о рюкзаке. Backpack problem презентация
Содержание
- 1. Задача о рюкзаке. Backpack problem
- 2. Вы грабитель.
- 3. Вы грабитель. Нужно выбрать вещи, которые Вы унесёте…
- 4. Вы грабитель. Нужно выбрать вещи, которые
- 5. Вы грабитель. Нужно выбрать вещи, которые
- 6. Вы грабитель. Нужно выбрать вещи, которые
- 7. 40$ 50$ 60$ 100$ 200$ 3 кг
- 8. 40$ 50$ 60$ 100$ 200$ 3 кг
- 9. 40$ 50$ 60$ 100$ 200$ 3 кг
- 10. 40$ 50$ 60$ 100$ 200$ 3 кг
- 11. 40$ 50$ 60$ 100$ 200$ 3 кг
- 12. Формат ввода: N M m1
- 13. Формат ввода: N M m1
- 14. Формат ввода: N M m1
- 15. Подход 1. Полный перебор Сколько всего вариантов?
- 16. Подход 1. Полный перебор Сколько всего вариантов?
- 17. Подход 1. Полный перебор Всего 2n вариантов
- 18. Подход 1. Полный перебор Даёт верный результат
- 19. Подход 2. Брать самую дорогую вещь Не
- 20. Подход 3. Рассчитать плотность каждой вещи: сi/mi.
- 21. Подход 3. Рассчитать плотность каждой вещи: сi/mi.
- 22. Подходы 2-3. Последние два алгоритма назывались жадными.
- 23. Подход 4. Метод динамического программирования. 40$ 50$
- 24. Подход 4. Метод динамического программирования. Заведём
- 25. Подход 4. Метод динамического программирования. Заведём
- 26. В P[i][j] будем хранить максимальную сумму, которую
- 27. В P[i][j] будем хранить максимальную сумму, которую
- 28. В P[i][j] будем хранить максимальную сумму, которую
- 29. В P[i][j] будем хранить максимальную сумму, которую
- 30. В P[i][j] будем хранить максимальную сумму, которую
- 31. Сначала заполним очевидное: нулевой столбец и нулевую
- 32. Сначала заполним очевидное: нулевой столбец и нулевую
- 33. Сначала заполним очевидное: нулевой столбец и нулевую
- 34. Сначала заполним очевидное: нулевой столбец и нулевую
- 35. Допустим, мы вычислили всё до i-ой строки
- 36. Есть два варианта 40$ 50$ 3 кг
- 37. Есть два варианта 40$ 50$ 3 кг
- 38. Есть два варианта 40$ 50$ 3 кг
- 39. Есть два варианта 40$ 50$ 3 кг
- 40. Есть два варианта 40$ 50$ 3 кг
- 41. Есть два варианта 40$ 50$ 3 кг
- 42. Есть два варианта 40$ 50$ 3 кг
- 43. Есть два варианта 40$ 50$ 3 кг
- 44. Есть два варианта 40$ 50$ 3 кг
- 45. Есть два варианта 40$ 50$ 3 кг
- 46. Есть два варианта 40$ 50$ 3 кг
- 47. Есть два варианта 40$ 50$ 3 кг
- 48. Есть два варианта 40$ 50$ 3 кг
- 49. Есть два варианта 40$ 50$ 3 кг
- 50. Есть два варианта 40$ 50$ 3 кг
- 51. Есть два варианта 40$ 50$ 3 кг
- 52. Есть два варианта 40$ 50$ 3 кг
- 53. Есть два варианта 40$ 50$ 3 кг
- 54. Есть два варианта 40$ 50$ 3 кг
Слайд 4Вы грабитель.
Нужно выбрать вещи, которые Вы унесёте…
40$
50$
60$
100$
200$
У всех вещей есть цены.
Слайд 5Вы грабитель.
Нужно выбрать вещи, которые Вы унесёте…
40$
50$
60$
100$
200$
У всех вещей есть цены.
Но у вещей есть ещё и вес!
3 кг
3 кг
5 кг
12 кг
18 кг
Слайд 6Вы грабитель.
Нужно выбрать вещи, которые Вы унесёте…
40$
50$
60$
100$
200$
У всех вещей есть цены.
Но у вещей есть ещё и вес!
3 кг
3 кг
5 кг
12 кг
18 кг
У рюкзака ограниченная вместимость
20
Слайд 12Формат ввода:
N M
m1 m2 … mn
c1
N – количество вещей
M – вместимость рюкзака
mi – вес i-ой вещи
ci – стоимость i-ой вещи
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг
Слайд 13Формат ввода:
N M
m1 m2 … mn
c1
N – количество вещей
M – вместимость рюкзака
mi – вес i-ой вещи
ci – стоимость i-ой вещи
Пример:
20
3 5 12 18
40 50 60 100 200
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг
Слайд 14Формат ввода:
N M
m1 m2 … mn
c1
N – количество вещей
M – вместимость рюкзака
mi – вес i-ой вещи
ci – стоимость i-ой вещи
Формат вывода:
Одно число – максимальная стоимость кражи
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг
Слайд 16Подход 1.
Полный перебор
Сколько всего вариантов?
Каждый предмет мы можем взять или не
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг
+
-
+
-
+
-
+
-
+
-
Слайд 18Подход 1.
Полный перебор
Даёт верный результат
Оооочень долго
(при n = 100 суперкомпьютер будет
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг
+
-
+
-
+
-
+
-
+
-
Слайд 19Подход 2.
Брать самую дорогую вещь
Не всегда будет давать максимальный ответ
(уже в
Приведите пример из трёх вещей
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг
Слайд 20Подход 3.
Рассчитать плотность каждой вещи: сi/mi.
Брать вещи, в порядке убывания плотности,
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг
Слайд 21Подход 3.
Рассчитать плотность каждой вещи: сi/mi.
Брать вещи, в порядке убывания плотности,
Тоже не всегда будет давать правильный ответ. (приведите пример)
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг
Слайд 22Подходы 2-3.
Последние два алгоритма назывались жадными.
Для данной задачи они не подходят.
40$
50$
60$
100$
200$
3
3 кг
5 кг
12 кг
18 кг
Слайд 24Подход 4.
Метод динамического программирования.
Заведём табличку (N + 1) x (M +
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг
Слайд 25Подход 4.
Метод динамического программирования.
Заведём табличку P:(N + 1) x (M +
Будем считать, что все вещи пронумерованы.
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг
Слайд 26В P[i][j] будем хранить максимальную сумму, которую можно заработать, выбирая среди
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг
Слайд 27В P[i][j] будем хранить максимальную сумму, которую можно заработать, выбирая среди
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг
Что будет здесь?
Слайд 28В P[i][j] будем хранить максимальную сумму, которую можно заработать, выбирая среди
40$
50$
3 кг
3 кг
Выбираем среди первых двух вещей
Слайд 29В P[i][j] будем хранить максимальную сумму, которую можно заработать, выбирая среди
40$
50$
3 кг
3 кг
Выбираем среди первых двух вещей.
Рюкзак вместимостью 4 кг.
Слайд 30В P[i][j] будем хранить максимальную сумму, которую можно заработать, выбирая среди
40$
50$
3 кг
3 кг
Слайд 31Сначала заполним очевидное: нулевой столбец и нулевую строку.
Как?
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12
Слайд 32Сначала заполним очевидное: нулевой столбец и нулевую строку.
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12
Слайд 33Сначала заполним очевидное: нулевой столбец и нулевую строку.
Будем заполнять оставшуюся часть
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Слайд 34Сначала заполним очевидное: нулевой столбец и нулевую строку.
Будем заполнять оставшуюся часть
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Слайд 35Допустим, мы вычислили всё до i-ой строки и j-го столбца.
Сейчас вычисляем
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Слайд 37Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i (последнюю)
Не брать
Слайд 38Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i (последнюю)
Не брать
Вычислим эти значения и выберем наибольшее
Слайд 39Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Только, если влезает.
Что это значит?
Слайд 40Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Только, если влезает
wi ≤ j
Слайд 41Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Мы точно зарабатываем: ci
Слайд 42Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Плюс, у нас осталось еще свободное место…
Слайд 43Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Плюс, у нас осталось еще свободное место…
Сколько?
wi
j
Слайд 45Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Как его оптимально заполнить?
wi
j
Слайд 46Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Таблица P знает ответ на этот вопрос!
wi
j
Слайд 47Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
В ячейке P[…][…] уже лежит лучшая сумма
wi
j
Слайд 48Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
В ячейке P[…][j-wi] уже лежит лучшая сумма
wi
j
Слайд 49Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
В ячейке P[i-1][j-wi] уже лежит лучшая сумма
wi
j
Слайд 50Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Итого:
ci + P[i-1][j-wi],
если влезет
wi
j
Слайд 51Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Итого:
ci + P[i-1][j-wi],
если влезет
Слайд 52Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Итого:
ci + P[i-1][j-wi],
если влезет
В ячейке P[…][…] уже есть ответ на эту задачу
Слайд 53Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Итого:
ci + P[i-1][j-wi],
если влезет
В ячейке P[i-1][…] уже есть ответ на эту задачу
Слайд 54Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Итого:
ci + P[i-1][j-wi],
если влезет
В ячейке P[i-1][j] уже есть ответ на эту задачу
