Відмінності між версіями «Задача про рюкзак.»

Матеріал з Вікі ЦДУ
Перейти до: навігація, пошук
(Задача про рюкзак.)
(Задача про рюкзак.)
Рядок 6: Рядок 6:
 
<center> <math> \max F=\sum_{j=1}^n w_j x_j </math> </center>
 
<center> <math> \max F=\sum_{j=1}^n w_j x_j </math> </center>
  
<center> <math> \sum_{j=1}^n m_j x_j /le M </math> ; </center>
+
<center> <math> \sum_{j=1}^n m_j x_j \le M </math> ; </center>

Версія за 21:41, 4 травня 2012

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

Найпростішою задачею цілочислового програмування, а саме задачею лише з одним обмеженням, є задача про рю-кзак (або ранець). Така задача має багато прикладів прак-тичного застосування. Назва «задача про рюкзак» пов’язана з інтерпретацією задачі вибору найкращого складу предметів, що задовольняють певні умови гіпотетичної проблеми туриста щодо вибору для походу оптимальної кількості речей.
Турист може вибирати потрібні речі із списку з Неможливо розібрати вираз (невідома помилка): n

предметів. Відома вага кожного Неможливо розібрати вираз (невідома помилка): j

-го предмета Неможливо розібрати вираз (невідома помилка): m_j(j=\overline{1,n}) .Визначена також цінність кожного виду предметів Неможливо розібрати вираз (невідома помилка): w_j .Максимальна вага всього вантажу в рюкзаку не може перевищувати зазначеного обсягу М. Необхідно визначити, скільки предметів кожного виду турист має покласти в рюкзак, щоб загальна цінність спорядження була максимальною за умови виконання обмеження на вагу рюкзака.
Позначимо через Неможливо розібрати вираз (невідома помилка): x_j – кількість предметів Неможливо розібрати вираз (невідома помилка): j -го виду в рюкзаку. Тоді математична модель задачі матиме вигляд:

Неможливо розібрати вираз (невідома помилка): \max F=\sum_{j=1}^n w_j x_j
Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^n m_j x_j \le M ;