- Задача о рюкзаке. Backpack problem
Содержание
- 2. Вы грабитель.
- 3. Вы грабитель. Нужно выбрать вещи, которые Вы унесёте…
- 4. Вы грабитель. Нужно выбрать вещи, которые Вы унесёте… 40$ 50$ 60$ 100$ 200$ У всех вещей
- 5. Вы грабитель. Нужно выбрать вещи, которые Вы унесёте… 40$ 50$ 60$ 100$ 200$ У всех вещей
- 6. Вы грабитель. Нужно выбрать вещи, которые Вы унесёте… 40$ 50$ 60$ 100$ 200$ У всех вещей
- 7. 40$ 50$ 60$ 100$ 200$ 3 кг 3 кг 5 кг 12 кг 18 кг 20
- 8. 40$ 50$ 60$ 100$ 200$ 3 кг 3 кг 5 кг 12 кг 18 кг 20
- 9. 40$ 50$ 60$ 100$ 200$ 3 кг 3 кг 5 кг 12 кг 18 кг 20
- 10. 40$ 50$ 60$ 100$ 200$ 3 кг 3 кг 5 кг 12 кг 18 кг 20
- 11. 40$ 50$ 60$ 100$ 200$ 3 кг 3 кг 5 кг 12 кг 18 кг 20
- 12. Формат ввода: N M m1 m2 … mn c1 c2 … cn N – количество вещей
- 13. Формат ввода: N M m1 m2 … mn c1 c2 … cn N – количество вещей
- 14. Формат ввода: N M m1 m2 … mn c1 c2 … cn N – количество вещей
- 15. Подход 1. Полный перебор Сколько всего вариантов? 40$ 50$ 60$ 100$ 200$ 3 кг 3 кг
- 16. Подход 1. Полный перебор Сколько всего вариантов? Каждый предмет мы можем взять или не взять… 40$
- 17. Подход 1. Полный перебор Всего 2n вариантов 40$ 50$ 60$ 100$ 200$ 3 кг 3 кг
- 18. Подход 1. Полный перебор Даёт верный результат Оооочень долго (при n = 100 суперкомпьютер будет вычислять
- 19. Подход 2. Брать самую дорогую вещь Не всегда будет давать максимальный ответ (уже в нашем примере
- 20. Подход 3. Рассчитать плотность каждой вещи: сi/mi. Брать вещи, в порядке убывания плотности, пока влезают. 40$
- 21. Подход 3. Рассчитать плотность каждой вещи: сi/mi. Брать вещи, в порядке убывания плотности, пока влезают. Тоже
- 22. Подходы 2-3. Последние два алгоритма назывались жадными. Для данной задачи они не подходят. 40$ 50$ 60$
- 23. Подход 4. Метод динамического программирования. 40$ 50$ 60$ 100$ 200$ 3 кг 3 кг 5 кг
- 24. Подход 4. Метод динамического программирования. Заведём табличку (N + 1) x (M + 1) 40$ 50$
- 25. Подход 4. Метод динамического программирования. Заведём табличку P:(N + 1) x (M + 1) Будем считать,
- 26. В P[i][j] будем хранить максимальную сумму, которую можно заработать, выбирая среди первых i вещей и имея
- 27. В P[i][j] будем хранить максимальную сумму, которую можно заработать, выбирая среди первых i вещей и имея
- 28. В P[i][j] будем хранить максимальную сумму, которую можно заработать, выбирая среди первых i вещей и имея
- 29. В P[i][j] будем хранить максимальную сумму, которую можно заработать, выбирая среди первых i вещей и имея
- 30. В P[i][j] будем хранить максимальную сумму, которую можно заработать, выбирая среди первых i вещей и имея
- 31. Сначала заполним очевидное: нулевой столбец и нулевую строку. Как? 40$ 50$ 3 кг 3 кг 60$
- 32. Сначала заполним очевидное: нулевой столбец и нулевую строку. 40$ 50$ 3 кг 3 кг 60$ 100$
- 33. Сначала заполним очевидное: нулевой столбец и нулевую строку. Будем заполнять оставшуюся часть сверху-вниз, слева-направо. 40$ 50$
- 34. Сначала заполним очевидное: нулевой столбец и нулевую строку. Будем заполнять оставшуюся часть сверху-вниз, слева-направо, выражая каждый
- 35. Допустим, мы вычислили всё до i-ой строки и j-го столбца. Сейчас вычисляем P[i][j]. 40$ 50$ 3
- 36. Есть два варианта 40$ 50$ 3 кг 3 кг 60$ 100$ 200$ 5 кг 12 кг
- 37. Есть два варианта 40$ 50$ 3 кг 3 кг 60$ 100$ 200$ 5 кг 12 кг
- 38. Есть два варианта 40$ 50$ 3 кг 3 кг 60$ 100$ 200$ 5 кг 12 кг
- 39. Есть два варианта 40$ 50$ 3 кг 3 кг 60$ 100$ 200$ 5 кг 12 кг
- 40. Есть два варианта 40$ 50$ 3 кг 3 кг 60$ 100$ 200$ 5 кг 12 кг
- 41. Есть два варианта 40$ 50$ 3 кг 3 кг 60$ 100$ 200$ 5 кг 12 кг
- 42. Есть два варианта 40$ 50$ 3 кг 3 кг 60$ 100$ 200$ 5 кг 12 кг
- 43. Есть два варианта 40$ 50$ 3 кг 3 кг 60$ 100$ 200$ 5 кг 12 кг
- 44. Есть два варианта 40$ 50$ 3 кг 3 кг 60$ 100$ 200$ 5 кг 12 кг
- 45. Есть два варианта 40$ 50$ 3 кг 3 кг 60$ 100$ 200$ 5 кг 12 кг
- 46. Есть два варианта 40$ 50$ 3 кг 3 кг 60$ 100$ 200$ 5 кг 12 кг
- 47. Есть два варианта 40$ 50$ 3 кг 3 кг 60$ 100$ 200$ 5 кг 12 кг
- 48. Есть два варианта 40$ 50$ 3 кг 3 кг 60$ 100$ 200$ 5 кг 12 кг
- 49. Есть два варианта 40$ 50$ 3 кг 3 кг 60$ 100$ 200$ 5 кг 12 кг
- 50. Есть два варианта 40$ 50$ 3 кг 3 кг 60$ 100$ 200$ 5 кг 12 кг
- 51. Есть два варианта 40$ 50$ 3 кг 3 кг 60$ 100$ 200$ 5 кг 12 кг
- 52. Есть два варианта 40$ 50$ 3 кг 3 кг 60$ 100$ 200$ 5 кг 12 кг
- 53. Есть два варианта 40$ 50$ 3 кг 3 кг 60$ 100$ 200$ 5 кг 12 кг
- 55. Скачать презентацию
Вы грабитель.
Вы грабитель.
Вы грабитель.
Нужно выбрать вещи, которые Вы унесёте…
Вы грабитель.
Нужно выбрать вещи, которые Вы унесёте…
Вы грабитель.
Нужно выбрать вещи, которые Вы унесёте…
40$
50$
60$
100$
200$
У всех вещей есть цены.
Вы грабитель.
Нужно выбрать вещи, которые Вы унесёте…
40$
50$
60$
100$
200$
У всех вещей есть цены.
Вы грабитель.
Нужно выбрать вещи, которые Вы унесёте…
40$
50$
60$
100$
200$
У всех вещей есть цены.
Вы грабитель.
Нужно выбрать вещи, которые Вы унесёте…
40$
50$
60$
100$
200$
У всех вещей есть цены.
Вы грабитель.
Нужно выбрать вещи, которые Вы унесёте…
40$
50$
60$
100$
200$
У всех вещей есть цены.
Вы грабитель.
Нужно выбрать вещи, которые Вы унесёте…
40$
50$
60$
100$
200$
У всех вещей есть цены.
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг
20
Max: 150$?
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг
20
Max: 150$?
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг
20
Max: 190$?
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг
20
Max: 190$?
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг
20
Max: 200$?
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг
20
Max: 200$?
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг
20
Max: 210$!
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг
20
Max: 210$!
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг
20
Max: 210$!
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг
20
Max: 210$!
Формат ввода:
N M
m1 m2 … mn
c1 c2 … cn
N – количество
Формат ввода:
N M
m1 m2 … mn
c1 c2 … cn
N – количество
Формат ввода:
N M
m1 m2 … mn
c1 c2 … cn
N – количество
Формат ввода:
N M
m1 m2 … mn
c1 c2 … cn
N – количество
Формат ввода:
N M
m1 m2 … mn
c1 c2 … cn
N – количество
Формат ввода:
N M
m1 m2 … mn
c1 c2 … cn
N – количество
Подход 1.
Полный перебор
Сколько всего вариантов?
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг
Подход 1.
Полный перебор
Сколько всего вариантов?
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг
Подход 1.
Полный перебор
Сколько всего вариантов?
Каждый предмет мы можем взять или не
Подход 1.
Полный перебор
Сколько всего вариантов?
Каждый предмет мы можем взять или не
Подход 1.
Полный перебор
Всего 2n вариантов
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг
+
-
+
-
+
-
+
-
+
-
Подход 1.
Полный перебор
Всего 2n вариантов
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг
+
-
+
-
+
-
+
-
+
-
Подход 1.
Полный перебор
Даёт верный результат
Оооочень долго
(при n = 100 суперкомпьютер будет
Подход 1.
Полный перебор
Даёт верный результат
Оооочень долго
(при n = 100 суперкомпьютер будет
Подход 2.
Брать самую дорогую вещь
Не всегда будет давать максимальный ответ
(уже в
Подход 2.
Брать самую дорогую вещь
Не всегда будет давать максимальный ответ
(уже в
Подход 3.
Рассчитать плотность каждой вещи: сi/mi.
Брать вещи, в порядке убывания плотности,
Подход 3.
Рассчитать плотность каждой вещи: сi/mi.
Брать вещи, в порядке убывания плотности,
Подход 3.
Рассчитать плотность каждой вещи: сi/mi.
Брать вещи, в порядке убывания плотности,
Подход 3.
Рассчитать плотность каждой вещи: сi/mi.
Брать вещи, в порядке убывания плотности,
Подходы 2-3.
Последние два алгоритма назывались жадными.
Для данной задачи они не подходят.
40$
50$
60$
100$
200$
3
Подходы 2-3.
Последние два алгоритма назывались жадными.
Для данной задачи они не подходят.
40$
50$
60$
100$
200$
3
Подход 4.
Метод динамического программирования.
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг
Подход 4.
Метод динамического программирования.
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг
Подход 4.
Метод динамического программирования.
Заведём табличку (N + 1) x (M +
Подход 4.
Метод динамического программирования.
Заведём табличку (N + 1) x (M +
Подход 4.
Метод динамического программирования.
Заведём табличку P:(N + 1) x (M +
Подход 4.
Метод динамического программирования.
Заведём табличку P:(N + 1) x (M +
![В P[i][j] будем хранить максимальную сумму, которую можно заработать, выбирая среди](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1459580/slide-25.jpg)
В P[i][j] будем хранить максимальную сумму, которую можно заработать, выбирая среди
В P[i][j] будем хранить максимальную сумму, которую можно заработать, выбирая среди
![В P[i][j] будем хранить максимальную сумму, которую можно заработать, выбирая среди](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1459580/slide-26.jpg)
В P[i][j] будем хранить максимальную сумму, которую можно заработать, выбирая среди
В P[i][j] будем хранить максимальную сумму, которую можно заработать, выбирая среди
![В P[i][j] будем хранить максимальную сумму, которую можно заработать, выбирая среди](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1459580/slide-27.jpg)
В P[i][j] будем хранить максимальную сумму, которую можно заработать, выбирая среди
В P[i][j] будем хранить максимальную сумму, которую можно заработать, выбирая среди
![В P[i][j] будем хранить максимальную сумму, которую можно заработать, выбирая среди](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1459580/slide-28.jpg)
В P[i][j] будем хранить максимальную сумму, которую можно заработать, выбирая среди
В P[i][j] будем хранить максимальную сумму, которую можно заработать, выбирая среди
![В P[i][j] будем хранить максимальную сумму, которую можно заработать, выбирая среди](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1459580/slide-29.jpg)
В P[i][j] будем хранить максимальную сумму, которую можно заработать, выбирая среди
В P[i][j] будем хранить максимальную сумму, которую можно заработать, выбирая среди
Сначала заполним очевидное: нулевой столбец и нулевую строку.
Как?
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12
Сначала заполним очевидное: нулевой столбец и нулевую строку.
Как?
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12
Сначала заполним очевидное: нулевой столбец и нулевую строку.
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12
Сначала заполним очевидное: нулевой столбец и нулевую строку.
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12
Сначала заполним очевидное: нулевой столбец и нулевую строку.
Будем заполнять оставшуюся часть
Сначала заполним очевидное: нулевой столбец и нулевую строку.
Будем заполнять оставшуюся часть
Сначала заполним очевидное: нулевой столбец и нулевую строку.
Будем заполнять оставшуюся часть
Сначала заполним очевидное: нулевой столбец и нулевую строку.
Будем заполнять оставшуюся часть
Допустим, мы вычислили всё до i-ой строки и j-го столбца.
Сейчас вычисляем
Допустим, мы вычислили всё до i-ой строки и j-го столбца.
Сейчас вычисляем
Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i (последнюю)
Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i (последнюю)
Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i (последнюю)
Не брать
Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i (последнюю)
Не брать
Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i (последнюю)
Не брать
Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i (последнюю)
Не брать
Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь
Признаки подобия треугольников. Задачи
Статистические показатели
Решение неравенств второй степени. Подготовка к ГИА. 9 класс
Введение в математический анализ
Равнобедренный треугольник
Решение задач на комбинации многогранников и тел вращения
Определение производной
Решение графических задач на газовые законы
Роль математики в будущей жизни учеников
Движение в геометрии
Разбор заданий В4 Работа выполнена ученицей 11 «А» класса МОУ «СОШ №47» г.Саратова Акимовой Светланой Константиновной Руководите
Движение. Его виды и применение. 9 класс
Двугранный угол
Теория матричных игр
Многочлен и его стандартный вид
Задача на логику
Геометрическое место точек
Единицы измерения длины. Сантиметр
Возникновение геометрии
Hypothesis Testing with Two Samples
Окружность и круг. Решение задач
Треугольник. Повторение. Задачи на проверку истинности утверждений
Показательные неравенства
Системы линейных уравнений. Матрицы
Задачи на смекалку
Интерактивная раскраска. Математическая игра для детей
Решение задач по теме «Векторы»
Параллельные прямые. Решение задач