Задача о рюкзаке. Backpack problem

Вы грабитель.

Вы грабитель.
Нужно выбрать вещи, которые Вы унесёте…

Вы грабитель.
Нужно выбрать вещи, которые Вы унесёте…
40$
50$
60$
100$
200$
У всех вещей есть цены. Суммарная стоимость украденного должна быть максимальной.

Вы грабитель.
Нужно выбрать вещи, которые Вы унесёте…
40$
50$
60$
100$
200$
У всех вещей есть цены. Суммарная стоимость украденного должна быть максимальной.
Но у вещей есть ещё и вес!
3 кг
3 кг
5 кг
12 кг
18 кг

Вы грабитель.
Нужно выбрать вещи, которые Вы унесёте…
40$
50$
60$
100$
200$
У всех вещей есть цены. Суммарная стоимость украденного должна быть максимальной.
Но у вещей есть ещё и вес!
3 кг
3 кг
5 кг
12 кг
18 кг
У рюкзака ограниченная вместимость
20

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: 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$!

Формат ввода:
N M
m1 m2 … mn
c1 c2 … cn
N – количество вещей
M – вместимость рюкзака
mi – вес i-ой вещи
ci – стоимость i-ой вещи
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг

Формат ввода:
N M
m1 m2 … mn
c1 c2 … cn
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 кг

Формат ввода:
N M
m1 m2 … mn
c1 c2 … cn
N – количество вещей
M – вместимость рюкзака
mi – вес i-ой вещи
ci – стоимость i-ой вещи
Формат вывода:
Одно число – максимальная стоимость кражи
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг

Подход 1.
Полный перебор
Сколько всего вариантов?
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг

Подход 1.
Полный перебор
Сколько всего вариантов?
Каждый предмет мы можем взять или не взять…
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 суперкомпьютер будет вычислять несколько тысяч лет)
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг
+
-
+
-
+
-
+
-
+
-

Подход 2.
Брать самую дорогую вещь
Не всегда будет давать максимальный ответ
(уже в нашем примере не работало)
Приведите пример из трёх вещей
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг

Подход 3.
Рассчитать плотность каждой вещи: сi/mi.
Брать вещи, в порядке убывания плотности, пока влезают.
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг

Подход 3.
Рассчитать плотность каждой вещи: сi/mi.
Брать вещи, в порядке убывания плотности, пока влезают.
Тоже не всегда будет давать правильный ответ. (приведите пример)
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг

Подходы 2-3.
Последние два алгоритма назывались жадными.
Для данной задачи они не подходят.
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 + 1)
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг

Подход 4.
Метод динамического программирования.
Заведём табличку P:(N + 1) x (M + 1)
Будем считать, что все вещи пронумерованы.
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг

В P[i][j] будем хранить максимальную сумму, которую можно заработать, выбирая среди первых i вещей и имея рюкзак вместимостью j кг.
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг

В P[i][j] будем хранить максимальную сумму, которую можно заработать, выбирая среди первых i вещей и имея рюкзак вместимостью j кг.
40$
50$
60$
100$
200$
3 кг
3 кг
5 кг
12 кг
18 кг
Что будет здесь?

В P[i][j] будем хранить максимальную сумму, которую можно заработать, выбирая среди первых i вещей и имея рюкзак вместимостью j кг.
40$
50$
3 кг
3 кг
Выбираем среди первых двух вещей

В P[i][j] будем хранить максимальную сумму, которую можно заработать, выбирая среди первых i вещей и имея рюкзак вместимостью j кг.
40$
50$
3 кг
3 кг
Выбираем среди первых двух вещей.
Рюкзак вместимостью 4 кг.

В P[i][j] будем хранить максимальную сумму, которую можно заработать, выбирая среди первых i вещей и имея рюкзак вместимостью j кг.
40$
50$
3 кг
3 кг

Сначала заполним очевидное: нулевой столбец и нулевую строку.
Как?
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-го столбца.
Сейчас вычисляем P[i][j].
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг

Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i (последнюю)

Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i (последнюю)
Не брать вещь №i

Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i (последнюю)
Не брать вещь №i
Вычислим эти значения и выберем наибольшее

Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь №i
Только, если влезает.
Что это значит?

Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь №i
Только, если влезает
wi ≤ j

Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь №i
Мы точно зарабатываем: ci

Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь №i
Плюс, у нас осталось еще свободное место…

Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь №i
Плюс, у нас осталось еще свободное место…
Сколько?
wi
j

Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь №i
j - wi
wi
j

Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь №i
Как его оптимально заполнить?
wi
j

Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь №i
Таблица P знает ответ на этот вопрос!
wi
j

Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь №i
В ячейке P[…][…] уже лежит лучшая сумма
wi
j

Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь №i
В ячейке P[…][j-wi] уже лежит лучшая сумма
wi
j

Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь №i
В ячейке P[i-1][j-wi] уже лежит лучшая сумма
wi
j

Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь №i
Итого:
ci + P[i-1][j-wi],
если влезет
wi
j

Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь №i
Итого:
ci + P[i-1][j-wi],
если влезет

Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь №i
Итого:
ci + P[i-1][j-wi],
если влезет
В ячейке P[…][…] уже есть ответ на эту задачу

Есть два варианта
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг
Взять вещь №i
Не брать вещь №i
Итого:
ci + P[i-1][j-wi],
если влезет
В ячейке P[i-1][…] уже есть ответ на эту задачу