Изменения

'''Непрерывный рюкзакЗадача о назначении''' (англ. ''Continuous knapsack problemGeneralized Assignment Problem'') - вариант задачиНаиболее общая задача семейства. Отличается от мультипликативного рюкзака тем, что каждый предмет имеет различные характеристики, в котором возможно брать любою дробную часть зависимости от рюкзака куда его помещают. Есть <math>N</math> предметов и <math>M</math> рюкзаков (<math>M\le N</math>). У каждого рюкзака своя вместимость <math>W_i</math>, у <tex> j </tex> предмета<tex> p_{ij} </tex> стоимость и вес, при этом удельная помещении его в <tex> i </tex> рюкзак, равны <tex> p_{ij} </tex> и <tex> w_{ij} </tex> соответвенно. Задача: выбрать <math>M</math> не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость сохраняетсябыла максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.Весьма важная задача, так как она моделирует оптимальное распределение различных задач, между вычислительными блоками.

:максимизировать общую стоимостьвыбранных предметов <math>\sum_{i=1}^M\sum_{j=1}^N p_{ij} x_{ij}.</math>:при выполнении условия совместности <math>\sum_{j=1}^N w_{ij} x_{ij} \le W_i \qquad i=1, \ldots, M</math>;:: <math>\sum_{i=1}^M x_{ij} \leq 1 \qquad j=1, \ldots, N</math>;::<math> x_{ij} \in \{0,1\} \qquad i=1, \ldots, N, \quad j=1, \ldots, N p_ix_i</math>;

Изменение формулировки значительно облегчает задачу. Жадный алгоритм дает оптимальное решение в данном случаеПрименение Динамического программирования нецелесообразно.