58
правок
Изменения
→Мультипликативный рюкзак
==Мультипликативный рюкзак==
'''Мультипликативный рюкзак''' (англ. ''Multiple Knapsack Problem'') - есть <math>N</math> предметов и <math>M</math> рюкзаков (<math>M\le N</math>). У каждого рюкзака своя вместимость <math>W_i</math>. Задача: выбрать <math>M</math> не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.
'''Пример:''' У транспортной компании есть парк машин разной грузоподъемности. Нужно перевезти товара на максимальную сумму с одного склада на другой единовременно.
===Формулировка Задачи===
максимизировать <math>\sum_{i=1}^M \sum_{j=1}^{N} p_jx_{ij}</math>
