Рюкзак. Восстановление ответа

Входные данные:
4 6 – количество, вместимость
2 4 1 2 - веса
7 2 5 1 – стоимости
Надо найти номера предметов, которые следует взять
Что получится?
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг

Входные данные:
4 6 – количество, вместимость
2 4 1 2 - веса
7 2 5 1 – стоимости
Надо найти номера предметов, которые следует взять
1
3
4
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг

Входные данные:
4 6 – количество, вместимость
2 4 1 2 - веса
7 2 5 1 – стоимости
Итак, мы построили таблицу. Как она будет выглядеть в нашем случае?
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг

Входные данные:
4 6 – количество, вместимость
2 4 1 2 - веса
7 2 5 1 – стоимости
Итак, мы построили таблицу. Как она будет выглядеть в нашем случае?
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг

Входные данные:
4 6 – количество, вместимость
2 4 1 2 - веса
7 2 5 1 – стоимости
Заполним первую строку…
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг

Входные данные:
4 6 – количество, вместимость
2 4 1 2 - веса
7 2 5 1 – стоимости
Заполним первую строку…
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг

Входные данные:
4 6 – количество, вместимость
2 4 1 2 - веса
7 2 5 1 – стоимости
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг

Входные данные:
4 6 – количество, вместимость
2 4 1 2 - веса
7 2 5 1 – стоимости
Какую максимальную сумму мы можем набрать?
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг

Входные данные:
4 6 – количество, вместимость
2 4 1 2 - веса
7 2 5 1 – стоимости
Какую максимальную сумму мы можем набрать?
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг

4 6 – количество, вместимость
2 4 1 2 - веса
7 2 5 1 – стоимости
Вспомним, как мы получили это число…
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг

4 6 – количество, вместимость
2 4 1 2 - веса
7 2 5 1 – стоимости
Либо не брать предмет №4…
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг

4 6 – количество, вместимость
2 4 1 2 - веса
7 2 5 1 – стоимости
Либо не брать предмет №4…
(Этот вариант не реализовался, т.к.
число другое)
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг

4 6 – количество, вместимость
2 4 1 2 - веса
7 2 5 1 – стоимости
Либо не брать предмет №4…
Либо взять предмет №4 и заполнить оставшееся место…
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг

4 6 – количество, вместимость
2 4 1 2 - веса
7 2 5 1 – стоимости
Либо не брать предмет №4…
Либо взять предмет №4 и заполнить оставшееся место…
40$
50$
3 кг
3 кг
60$
100$
200$
5 кг
12 кг

4 6 – количество, вместимость
2 4 1 2 - веса
7 2 5 1 – стоимости
Значит мы берем четвёртый предмет.
7$
2$
2 кг
4 кг
5$
1$
1 кг
2 кг

4 6 – количество, вместимость
2 4 1 2 - веса
7 2 5 1 – стоимости
Меняем текущую ячейку.
7$
2$
2 кг
4 кг
5$
1$
1 кг
2 кг

4 6 – количество, вместимость
2 4 1 2 - веса
7 2 5 1 – стоимости
Аналогично
7$
2$
2 кг
4 кг
5$
1$
1 кг
2 кг

4 6 – количество, вместимость
2 4 1 2 - веса
7 2 5 1 – стоимости
Аналогично
7$
2$
2 кг
4 кг
5$
1$
1 кг
2 кг

4 6 – количество, вместимость
2 4 1 2 - веса
7 2 5 1 – стоимости
Аналогично
7$
2$
2 кг
4 кг
5$
1$
1 кг
2 кг

4 6 – количество, вместимость
2 4 1 2 - веса
7 2 5 1 – стоимости
Аналогично
7$
2$
2 кг
4 кг
5$
1$
1 кг
2 кг

4 6 – количество, вместимость
2 4 1 2 - веса
7 2 5 1 – стоимости
Аналогично
7$
2$
2 кг
4 кг
5$
1$
1 кг
2 кг

4 6 – количество, вместимость
2 4 1 2 - веса
7 2 5 1 – стоимости
Аналогично
7$
2$
2 кг
4 кг
5$
1$
1 кг
2 кг

4 6 – количество, вместимость
2 4 1 2 - веса
7 2 5 1 – стоимости
Аналогично
7$
2$
2 кг
4 кг
5$
1$
1 кг
2 кг

4 6 – количество, вместимость
2 4 1 2 - веса
7 2 5 1 – стоимости
Аналогично
7$
2$
2 кг
4 кг
5$
1$
1 кг
2 кг