Теория сложностей вычислительных процессов и структур
Лабораторная работа №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


назад