06_continuous_backpack.py

Задача о рюкзаке(англ. Knapsack problem) — дано N предметов, n_i предмет имеет массу  
w_i > 0 и стоимость p_i > 0. 
Необходимо выбрать из этих предметов такой набор, чтобы 
суммарная масса не превосходила заданной величины W 
(вместимость рюкзака), а суммарная стоимость была максимальна. 

Непрерывный рюкзак (англ. Continuous knapsack problem) - 
вариант задачи, в котором возможно брать любою дробную часть от предмета, при этом удельная стоимость сохраняется.

Пример: Вор грабит мясника. Суммарно он может унести ограниченный вес товаров. 
Вор может резать товары без ущерба к удельной стоимости. Нужно унести товара на максимальную сумму.

Формулировка Задачи

Задача выбрать часть x_i каждого предмета так, чтобы

    максимизировать общую стоимость: \sum_{i=1}^N p_ix_i; 

    выполнялось условие совместности: \sum_{i=1}^N w_ix_i \le W; 

где 0 \le x_i \le 1 дробное, для всех i= 1,2,...,N.

Варианты решения :

Возможность брать любую часть от предмета сильно упрощает задачу. 
Жадный алгоритм дает оптимальное решение в данном случае.

Реализация часть псевдокода :

sort(); // сортируем в порядке убывания удельной стоимости //сортировка отношения 
for i = 1..N // идем по предметам            
      if W >= w[i]    //если помещается - берем
       sum += p[i];
       W -= w[i];
   else
       sum += W / w[i] * p[i];// иначе берем сколько можно и выходим
       break;
       
Дано: 
1)

2 2

10 4

10 4

Результат:

5.0

2)

3 50

60 20

100 50

120 30

Результат:

180.0

3) 

0 0

Результат:

0.0