58
правок
Изменения
→Другие задачи семейства
Задача выбрать число <tex>x_i</tex> предметов каждого типа так, чтобы
* максимизировать общую стоимость: <tex>\sum_{i=1}^N p_ix_i</tex>
* выполнялось условие на совместность: <tex>\sum_{i=1}^N w_ix_i \le W</tex>
===Варианты решения===
При небольших <tex>b_i</tex> решается сведением к классической задаче о рюкзаке. В иных случаях:
* Методом ветвей и границ.* Методом динамического программирования.
===Метод динамического программирования===
Тогда меняя i от 1 до <tex>N</tex>, расчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 0 до <tex>W</tex>, по рекурентной формуле:
<tex>d(i,c) = max(d(i - 1, c - lw_i) + lp_i : ) </tex> по всем целым <tex> l\ integer</tex> из промежутка <tex>0 \le l \le min(b_i,\lfloor c/w_i \rfloor))</tex>
Если не нужно востанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного.
=== Реализация ===
for i = 0..W // база
d[0][i] = 0; for i = 1..N
for c = 0..W //Перебираем для каждого i, все вместисмости
d[i][c] = d[i - 1][c];
for l = min(b[i], c / w[i]) .. 1 // ищем l для которого выполняется максимум
d[i][c] = max(d[i][c], d[i - 1][c - l * w[i]] + p[i] * l);
==Не ограниченный Неограниченный рюкзак=='''Не ограниченный Неограниченный рюкзак''' (англ.''Unbounded Knapsack Proble'') - обобщение ограниченого рюкзака, в котором любой предмет может быть выбран любое количество раз.
'''Пример:''' перекупщик закупается на оптовой базе. Он может увезти ограниченное количество товара, количество товара каждого типа на базе не ограниченно. Нужно увезти товара на максимальную сумму.
Задача выбрать количество <tex>x_i</tex> предметов каждого типа так, чтобы
*максимизировать общую стоимость: <tex>\sum_{i=1}^N p_ix_i</tex>
*выполнялось условие на совместность: <tex>\sum_{i=1}^N w_ix_i \le W</tex>
<tex> x_i \ge 0 </tex> целое, для всех <tex> i= 1,2,...,N</tex>
===Варианты решения===
Самые распространенные методы точного решения это:
* Метод ветвей и границ.* Метод динамического программирования.
===Метод динамического программирования===
<tex> d(c) = max(d(c), d(c - w_i) + p_i) </tex>
Задача выбрать часть <tex>x_i</tex> каждого предмета так, чтобы
*максимизировать общую стоимость: <tex>\sum_{i=1}^N p_ix_i</tex>
*выполнялось условие на совместность: <tex>\sum_{i=1}^N w_ix_i \le W</tex>
<tex> 0 \le x_i \le 1</tex> дробное, для всех <tex> i= 1,2,...,N</tex>
===Варианты решения===
=== Реализация ===
sort() ; // сортируем в порядке убывания удельной стоимости.
for i = 1..N // идем по предметам
if W >= w[i] //если помещается - берем
summ += p[i]; W -= w[i];
else
summ += W / w[i] * p[i] ;// иначе берем сколько можно и выходим exitbreak;
==Задача о суммах подмножеств==
Нужно выбрать подмножество так, чтобы сумма ближе всего к <tex>W</tex>, но не превысила его. Более формально, нужно найти набор бинарных величин <tex>x_i</tex>, так чтобы
*максимизировать общую стоимость: <tex>\sum_{i=1}^N w_ix_i</tex>
*выполнялось условие на совместность: <tex>\sum_{i=1}^N w_ix_i \le W</tex>
<tex> x_i \ge 0 </tex> целое, для всех <tex> i= 1,2,...,N</tex>
===Варианты решения===
Для решения пригодны любые методы для классической задачи, однако специализированые алгоритмы, обычно более оптимальны по параметрам. Используется:
* Метод динамического программирования.* Гибридный метод на основе динамического программирования и поиска по дереву. Существуют алгоритмы основанные на этом методе со сложностью <tex> Omin(n2\log_{10}max(w_j), 0.7n) </tex> и <tex>min(2,5\log_{10}(max(w_j), 0.8n) </tex> в худшем случае.
===Метод динамического программирования===
Задача выбрать количество <tex>x_i</tex> предметов каждого типа так, чтобы
*минимизировать количество взятых предметов: <tex>\sum_{i=1}^N x_i</tex>
*сумма весов выбранных предметов равнялась вместимости рюкзака: <tex>\sum_{i=1}^N w_ix_i = W</tex>
<tex> x_i \ge 0 </tex> целое, для всех <tex> i= 1,2,...,N</tex>
===Варианты решения===
Самые распространенные методы точного решения это:
* Метод ветвей и границ.* Метод динамического программирования.
===Метод динамического программирования===
Математически задачу можно представить так:
*минимизировать количество рюкзаков: <tex>\sum_{i=1}^N y_i</tex>
*так чтобы выполнялось условие на совместность: <tex>\sum_{i=1}^N w_ix_{ij} \le Wy_j \qquad j \in {1, ..., N}</tex>
<tex>
'''Пример:''' У транспортной компании есть парк машин разной грузоподъемности. Нужно перевезти товара на максимальную сумму с одного склада на другой единовременно.
===Формулировка Задачи===
так , чтобы <tex>\sum_{i=1}^N w_jx_{ij} \le W_i</tex> выполнялось для всех <tex> i= 1,2,...,N</tex>,.
<tex>\sum_{j=1}^{M}x_{ij}=1</tex> для всех <tex> i= 1,2,...,N</tex>
===Формулировка Задачи===
===Варианты решения===
