Теория сложностей вычислительных процессов и структур |
Лабораторная работа №5 | назад |
Задачи динамического программирования. Задача грабителя (задача “о рюкзаке”)
Имеется склад, на котором присутствует некоторый ассортимент товаров. Запас каждого товара неограничен. У каждого товара своя стоимость Ci и масса mi. Написать программу, которая методом динамического программирования формирует такой набор товаров, чтобы его суммарная масса не превышала заданную грузоподъемность М, и стоимость была бы максимальной. На экран вывести промежуточные вычисления, сформированный набор, его стоимость и массу.
Номер варианта выбирается по последней цифре пароля.
Вариант 0
Номер товара, i |
mi |
Ci |
M |
1 |
13 |
36 |
52 |
2 |
18 |
51 |
|
3 |
3 |
8 |
|
4 |
8 |
22 |
Вариант 1
Номер товара, i |
mi |
Ci |
M |
1 |
3 |
8 |
49 |
2 |
8 |
22 |
|
3 |
10 |
28 |
Вариант 2
Номер товара, i |
mi |
Ci |
M |
1 |
8 |
22 |
49 |
2 |
10 |
28 |
|
3 |
14 |
40 |
Вариант 3
Номер товара, i |
mi |
Ci |
M |
1 |
11 |
9 |
47 |
2 |
9 |
8 |
|
3 |
12 |
3 |
Вариант 4
Номер товара, i |
mi |
Ci |
M |
1 |
14 |
40 |
53 |
2 |
13 |
36 |
|
3 |
18 |
51 |
|
4 |
4 |
11 |
Вариант 5
Номер товара, i |
mi |
Ci |
M |
1 |
14 |
40 |
50 |
2 |
4 |
11 |
|
3 |
8 |
22 |
|
4 |
10 |
28 |
Вариант 6
Номер товара, i |
mi |
Ci |
M |
1 |
10 |
28 |
48 |
2 |
13 |
36 |
|
3 |
5 |
13 |
|
4 |
14 |
40 |
Вариант 7
Номер товара, i |
mi |
Ci |
M |
1 |
13 |
36 |
50 |
2 |
5 |
13 |
Вариант 8
Номер товара, i |
mi |
Ci |
M |
1 |
8 |
22 |
53 |
2 |
13 |
36 |
Вариант 9
Номер товара, i |
mi |
Ci |
M |
1 |
13 |
36 |
47 |
2 |
3 |
8 |