Задача про рюкзак.
Матеріал з Вікі ЦДУ
Версія від 21:34, 4 травня 2012; Дмитриев Сергей (обговорення • внесок)
Задача про рюкзак.
Найпростішою задачею цілочислового програмування, а саме задачею лише з одним обмеженням, є задача про рю-кзак (або ранець). Така задача має багато прикладів прак-тичного застосування. Назва «задача про рюкзак» пов’язана з інтерпретацією задачі вибору найкращого складу предметів, що задовольняють певні умови гіпотетичної проблеми туриста щодо вибору для походу оптимальної кількості речей.
Турист може вибирати потрібні речі із списку з Неможливо розібрати вираз (невідома помилка): n
предметів. Відома вага кожного Неможливо розібрати вираз (невідома помилка): j
-го предмета Неможливо розібрати вираз (невідома помилка): m_j(j=\overline{1,n}) .Визначена також цінність кожного виду предметів Неможливо розібрати вираз (невідома помилка): w_j .
