Відмінності між версіями «Задача про рюкзак.»
(→Задача про рюкзак.) |
(→Задача про рюкзак.) |
||
| Рядок 3: | Рядок 3: | ||
Турист може вибирати потрібні речі із списку з <math>n</math> предметів. Відома вага кожного <math>j</math>-го предмета <math>m_j(j=\overline{1,n})</math>.Визначена також цінність кожного виду предметів <math>w_j</math>.Максимальна вага всього вантажу в рюкзаку не може перевищувати зазначеного обсягу М. Необхідно визначити, скільки предметів кожного виду турист має покласти в рюкзак, щоб загальна цінність спорядження була максимальною за умови виконання обмеження на вагу рюкзака.<br> | Турист може вибирати потрібні речі із списку з <math>n</math> предметів. Відома вага кожного <math>j</math>-го предмета <math>m_j(j=\overline{1,n})</math>.Визначена також цінність кожного виду предметів <math>w_j</math>.Максимальна вага всього вантажу в рюкзаку не може перевищувати зазначеного обсягу М. Необхідно визначити, скільки предметів кожного виду турист має покласти в рюкзак, щоб загальна цінність спорядження була максимальною за умови виконання обмеження на вагу рюкзака.<br> | ||
Позначимо через <math>x_j</math>– кількість предметів <math>j</math>-го виду в рюкзаку. Тоді математична модель задачі матиме вигляд: | Позначимо через <math>x_j</math>– кількість предметів <math>j</math>-го виду в рюкзаку. Тоді математична модель задачі матиме вигляд: | ||
| + | |||
| + | <center> <math> \max F=\sum_{j=1}^n w_j x_j </math> </center> | ||
Версія за 21:39, 4 травня 2012
Задача про рюкзак.
Найпростішою задачею цілочислового програмування, а саме задачею лише з одним обмеженням, є задача про рю-кзак (або ранець). Така задача має багато прикладів прак-тичного застосування. Назва «задача про рюкзак» пов’язана з інтерпретацією задачі вибору найкращого складу предметів, що задовольняють певні умови гіпотетичної проблеми туриста щодо вибору для походу оптимальної кількості речей.
Турист може вибирати потрібні речі із списку з Неможливо розібрати вираз (невідома помилка): n
предметів. Відома вага кожного Неможливо розібрати вираз (невідома помилка): j
-го предмета Неможливо розібрати вираз (невідома помилка): m_j(j=\overline{1,n})
.Визначена також цінність кожного виду предметів Неможливо розібрати вираз (невідома помилка): w_j
.Максимальна вага всього вантажу в рюкзаку не може перевищувати зазначеного обсягу М. Необхідно визначити, скільки предметів кожного виду турист має покласти в рюкзак, щоб загальна цінність спорядження була максимальною за умови виконання обмеження на вагу рюкзака.
Позначимо через Неможливо розібрати вираз (невідома помилка): x_j
– кількість предметів Неможливо розібрати вираз (невідома помилка): j
-го виду в рюкзаку. Тоді математична модель задачі матиме вигляд:
