58
правок
Изменения
→Непрерывный рюкзак
==Непрерывный рюкзак==
'''Непрерывный рюкзак''' (англ. ''Continuous knapsack problem'') - вариант задачи, в котором возможно брать любою дробную часть от предмета, при этом удельная стоимость сохраняется.
'''Пример:''' Вор грабит мясника. Суммарно он может унести ограниченный вес товаров. Вор может резать товары без ущерба к удельной стоимости. Нужно унести товара на максимальную сумму.
===Формулировка Задачи===
Задача выбрать часть <tex>x_i</tex> каждого предмета так, чтобы
===Варианты решения===
Изменение формулировки значительно облегчает задачу. Жадный алгоритм дает оптимальное решение в данном случае.
=== Реализация ===
sort() // сортируем в порядке убывания удельной стоимости.
for i = 1..N // идем по предметам
if W > w[i] //если помещается - берем
summ += p[i]
W -= w[i]
else
summ += W / w[i] * p[i] // иначе берем сколько можно и выходим
exit
==Задача о суммах подмножеств==
