СибГУТИ Лабораторная работа 3 Вариант 8 Теория сложности вычислительных процессов и структур скачать бесплатно

Задание

Имеется склад, на котором присутствует некоторый ассортимент товаров. Запас каждого товара неограничен. У каждого товара своя стоимость сi и масса mi. Написать программу, которая методом динамического программирования формирует набор товаров максимальной стоимости таким образом, чтобы его суммарная масса не превышала заданную грузоподъемность М.  

Вывести промежуточные вычисления, сформированный набор, его стоимость и массу.

Номер варианта выбирается по последней цифре пароля.

Вариант 8

Номер товара, i mi сi M

1 8 41 57

2 11 56

3 7 28 52

4 6 32

Описание алгоритма

Задача: Имеется склад, на котором есть некоторый ассортимент товаров. Запас каждого товара считается неограниченным. Товары имеют две характеристики: mi – масса, ci – стоимость;  .

Необходимо выбрать набор товаров так, чтобы его суммарная масса не превосходила заранее фиксированную массу М (т.е.  ), и стоимость набора была как можно больше ( ).

Идея решения: Считаем, что все массы mi целочисленные. Решим эту задачу методом динамического программирования. Изобретаем метод, т.е. формулу:

Нам необходимо найти  , т.е. максимально возможную сумму  при заданном М. Предположим, что к этому моменту мы знаем, как решать эту задачу для всех меньших значений грузоподъемности. Тогда смотрим, какой товар мы положили в рюкзак последним. Если это был первый товар стоимостью с1, то мы должны оптимизировать стоимость рюкзака при грузоподъемности  . Если это был второй товар стоимостью с2 , то оптимизация при грузоподъемности  , и т.д. Среди всех этих величин выбираем максимальную.

Таким образом, получаем формулу:  

Текст программы на языке Pascal

...

Результаты работы программы

z:   0  0  0  0  0  0  0 41 41 41 41 41 41 41 41 82 82 82 82 82 82 82 82 123 123 123 123 123 123 123 123 164 164 164 164 164 164 164 164 205 205 205 205 205 205 205 205 246 246 246 246 246 246 246 246 287 287 

r:   0  0  0  0  0  0  0  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 

z:   0  0  0  0  0  0  0 41 41 41 56 56 56 56 56 82 82 82 97 97 97 112 112 123 123 123 138 138 138 153 153 164 168 168 179 179 179 194 194 205 209 209 220 224 224 235 235 246 250 250 261 265 265 276 280 287 291 

r:   0  0  0  0  0  0  0  1  1  1  2  2  2  2  2  1  1  1  2  2  2  2  2  1  1  1  2  2  2  2  2  1  2  2  2  2  2  2  2  1  2  2  2  2  2  2  2  1  2  2  2  2  2  2  2  1  2 

z:   0  0  0  0  0  0 28 41 41 41 56 56 56 56 69 82 82 84 97 97 97 112 112 123 123 125 138 138 140 153 153 164 168 168 179 179 181 194 194 205 209 209 220 224 224 235 235 246 250 250 261 265 265 276 280 287 291 

r:   0  0  0  0  0  0  3  1  1  1  2  2  2  2  3  1  1  3  2  2  2  2  2  1  1  3  2  2  3  2  2  1  2  2  2  2  3  2  2  1  2  2  2  2  2  2  2  1  2  2  2  2  2  2  2  1  2 

z:   0  0  0  0  0 32 32 41 41 41 56 64 64 73 73 82 88 96 97 105 105 114 120 128 129 137 138 146 152 160 161 169 170 178 184 192 193 201 202 210 216 224 225 233 234 242 248 256 257 265 266 274 280 288 289 297 298 

r:   0  0  0  0  0  4  4  1  1  1  2  4  4  4  4  1  4  4  2  4  4  4  4  4  4  4  2  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4 

Стоимость = 298

Вес = 57

Набор предметов:  4  4  4  4  4  2  1  1