58
правок
Изменения
→Другие задачи семейства
Сложность алгоритма <tex>O(NW)</tex>.
==Задача об упаковке==
'''Задача об упаковке''' (англ. ''Bin Packing Problem'') - имеются <tex> N </tex> рюкзаков вместимости <tex> W </tex> и столько же предметов с весами tex>w_i</tex>. Нужно распределить все предметы, задействовав минимальное количество рюкзаков.
===Формулировка Задачи===
Математически задачу можно представить так:
минимизировать количество рюкзаков: <math>\sum_{i=1}^N y_i</math>
так чтобы выполнялось условие на совместность:
<math>\sum_{i=1}^N w_ix_ij \le Wy_j \qquad j \in {1, ..., N}</math>
<tex>
x_ij
\begin{cases}
1 & \text{if j item is assigned to i knapsack};\\
0 & \text{else};
\end{cases}
</tex>
<math> 0 \le x_i \le 1</math> дробное, для всех <math> i= 1,2,...,N</math>
===Варианты решения===
Изменение формулировки значительно облегчает задачу. Жадный алгоритм дает оптимальное решение в данном случае.
==Мультипликативный рюкзак==
==Задача об упаковке==
'''Непрерывный рюкзак''' (англ. ''Continuous knapsack problem'') - вариант задачи, в котором возможно брать любою дробную часть от предмета, при этом удельная стоимость сохраняется.
===Формулировка Задачи===
Задача выбрать часть <tex>x_i</tex> каждого предмета так, чтобы
максимизировать общую стоимость: <math>\sum_{i=1}^N p_ix_i</math>
выполнялось условие на совместность: <math>\sum_{i=1}^N w_ix_i \le W</math>
<math> 0 \le x_i \le 1</math> дробное, для всех <math> i= 1,2,...,N</math>
===Варианты решения===
Изменение формулировки значительно облегчает задачу. Жадный алгоритм дает оптимальное решение в данном случае.
==Задача о назначении==
'''Непрерывный рюкзак''' (англ. ''Continuous knapsack problem'') - вариант задачи, в котором возможно брать любою дробную часть от предмета, при этом удельная стоимость сохраняется.
===Формулировка Задачи===
Задача выбрать часть <tex>x_i</tex> каждого предмета так, чтобы
максимизировать общую стоимость: <math>\sum_{i=1}^N p_ix_i</math>
выполнялось условие на совместность: <math>\sum_{i=1}^N w_ix_i \le W</math>
<math> 0 \le x_i \le 1</math> дробное, для всех <math> i= 1,2,...,N</math>
===Варианты решения===
Изменение формулировки значительно облегчает задачу. Жадный алгоритм дает оптимальное решение в данном случае.
= Литература =
