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

1.

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

2.

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

3.

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

4.

40$
Входные данные:
4 6 – количество, вместимость
2 4 1 2 - веса
7 2 5 1 – стоимости
3 кг
3 кг
Итак, мы построили таблицу. Как
она будет выглядеть в нашем случае?
0 1 2 3 4 5 6 j 8 9
10
11
12
13
14
15
16
17
18
19
20
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
2
0
i
0
4
0
5
0
0
0
0
0
0
0
0
0
0
50$
60$
5 кг
100$
x
x
12 кг
200$

5.

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

6.

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

7.

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

8.

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

9.

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

10.

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

11.

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

12.

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

13.

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

14.

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

15.

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

16.

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

17.

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

18.

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

19.

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

20.

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

21.

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

22.

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

23.

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

24.

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

25.

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

26.

7$
Немного о реализации
Переменные х, у – для хранения
текущей позиции
Пока х не достигло нуля:
• Сравниваем текущий результат
с верхним числом
• Если совпадает, перемещаемся
туда
• Если
нет,
перемещаем
в
соответствующее место (смотри
таблицу весов) и выводим
взятую вещь
2 кг
4 кг
2$
5$
1 кг
1$
2 кг