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

Лабораторная работа №3
Решение задачи о рюкзаке методом динамического программирования
Присылаемый на проверку архив должен содержать 2 файла:
 файл отчета, содержащий титульный лист, условие задачи, описание используемого алгоритма, исходный текст программы (с указанием языка реализации) и результаты работы программы (можно в виде скриншотов);
 файл с исходным текстом программы (программу можно писать на любом языке программирования).

1. Задание на лабораторную работу
Имеется склад, на котором присутствует некоторый ассортимент из 4 видов товаров. Запас каждого товара неограничен. У каждого товара своя стоимость c(i) и масса m(i).
Написать программу, которая методом динамического программирования формирует набор товаров максимальной стоимости таким образом, чтобы его суммарная масса не превышала заданную грузоподъемность М = 63. Программа должна выводить таблицу промежуточных вычислений, сформированный оптимальный набор предметов, его итоговую стоимость и массу.

2. Теоретическая часть и описание алгоритма
В данной работе рассматривается неограниченная задача о рюкзаке (Unbounded Knapsack Problem), поскольку запас каждого товара на складе неограничен (предметы одного и того же типа можно брать многократно).
Для решения задачи используется метод диначеского программирования. Вместо полного перебора всех комбинаций (который имеет экспоненциальную сложность) строится функция, определяющая максимальную ценность для каждого промежуточного веса от 0 до М.

Расчетная формула метода:
Пусть W — текущая вместимость рёкзака (изменяется от 0 до М). Обозначим через f(W) максимальную стоимость товаров, которую можно набрать в рюкзак весом W.
Формула имеет вид:
f(W) = максимум по всем предметам i (у которых масса m(i) <= W) от выражения:
f(W - m(i)) + c(i)
Где:
• f(W - m(i)) — максимальная стоимость рюкзака меньшего веса, оставшегося после добавления i-го предмета.
• c(i) — стоимость добавляемого i-го предмета.
База индукции:
Для рюкзака нулевой вместимости максимальная ценность равна нулю: f(0) = 0.
Для восстановления набора предметов параллельно заполняется массив решений S(W), куда записывается номер товара i, на котором был достигнут максимум стоимости для веса W. После заполнения массива от финальной вместимости М производится обратный шаг: берется товар из S(M), его вес вычитается из М, и процесс повторяется, пока свободное место не станет равным нулю.

3. Исходные данные (Вариант 6)
• Грузоподъемность рюкзака: M = 63
• Количество видов товаров: 4
Характеристики доступных товаров представлены в таблице:
Номер товара (i) Масса товара, m(i) Стоимость товара, c(i) Удельная ценность (c/m)
1 6 11 1.83
2 4 15 3.75
3 10 45 4.50
4 9 37 4.11

Лабораторная работа 3 20.09.2026 20.09.2026 Зачет Уважаемый, замечаний нет. Галкина Марина Юрьевна