Тема 13. Задача про рюкзак

Задача про рюкзак

Існує п предметів, кожний з яких важить a[i] і коштує c[i] (i = 1, 2 , ..., п). Потрібно завантажити рюкзак так, щоб сумарна вартість вкладених у нього предметів була максимальною, а вага рюкзака при цьому не перевищувала задане значення A.

Нехай x[1], x[2], … x[n] - змінні, які мають такий зміст:

x[i] = 1 , якщо і-й предмет завантажується;

x[i] = 0, якщо і-й предмет не завантажується

Математична модель задачі полягає у тому, щоб знайти такий набір значень змінних x[1], x[2], … x[n], який задовольняв би умови:

x[i] = 1 або x[i] = 0 для i = 1, 2 , ..., п

a[1]*x[1] + a[2]*x[2] + … + a[n]*x[n] <=A

при яких функція L = c[1]*x[1] + c[2]*x[2] + … + c[n]*x[n]  набуває максимального значення.

Завдання

Зібравшись на осінній рейд, пластун складає рюкзак з 6 продуктів таким чином:

вага рюкзака не повинна перевищувати 25 кг, вартість продуктів  не може перевищувати 100 грн, а кількість калорій взятих продуктів має бути максимальною. Решта даних дадати самостійно (для наочності у таблиці).

            Створити математичну модель такої задачі.