# Задача о дробном рюкзаке

!!! question

    Дано *n* предметов, где *i*-й предмет имеет массу *wgt*[*i*-1] и стоимость *val*[*i*-1], и рюкзак вместимостью *cap*. Каждый предмет можно выбрать только один раз, **но можно выбрать часть предмета, при этом стоимость рассчитывается пропорционально выбранной массе**. Требуется найти максимальную стоимость предметов в рюкзаке при ограниченной вместимости. Пример показан на рисунке ниже.

![Пример данных для задачи о дробном рюкзаке](../assets/media/image1036.jpeg)

Задача о дробном рюкзаке и задача о рюкзаке 0-1 в целом очень похожи: состояние включает текущий предмет *i* и вместимость *c*, цель -- найти максимальную стоимость при ограниченной вместимости рюкзака.

Отличие в том, что в данной задаче допускается выбирать часть предмета. Как показано на рисунке ниже, **можно произвольно разделять предметы и рассчитывать соответствующую стоимость пропорционально массе**.

1. Для предмета *i* его стоимость на единицу массы равна *val*[*i* - 1]/*wgt*[*i* - 1], сокращенно -- удельная стоимость.
2. Предположим, что в рюкзак помещена часть предмета *i* массой *w*, тогда увеличение стоимости рюкзака составит *w* × *val*[*i* - 1]/*wgt*[*i* - 1].

![Стоимость предметов на единицу массы](../assets/media/image1040.jpeg)

### Определение жадной стратегии

Максимизация общей стоимости предметов в рюкзаке, по сути, является максимизацией стоимости предметов на единицу массы. Из этого можно вывести жадную стратегию, изображенную на рисунке ниже.

1. Отсортировать предметы по убыванию стоимости на единицу массы.
2. Перебирать все предметы и **жадно выбирать на каждом этапе предмет с наивысшей стоимостью на единицу массы**.
3. Если оставшейся вместимости рюкзака недостаточно, использовать часть текущего предмета для заполнения рюкзака.

![Жадная стратегия для задачи о дробном рюкзаке](../assets/media/image1042.jpeg)

### Реализация кода

Мы создали класс предмета `Item` для сортировки предметов по стоимости на единицу массы. Выполняем цикл жадного выбора, прерываем его и возвращаем решение, когда рюкзак заполнен:

```src
[file]{fractional_knapsack}-[class]{}-[func]{fractional_knapsack}
```

Временная сложность встроенных алгоритмов сортировки обычно составляет *O*(*n* log *n*), пространственная сложность обычно *O*(log *n*) или *O*(*n*), в зависимости от конкретной реализации в языке программирования.

Помимо сортировки, в худшем случае необходимо перебрать весь список предметов, **поэтому временная сложность составляет *O*(*n*)**, где *n* -- количество предметов.

Поскольку инициализируется список объектов `Item`, **пространственная сложность составляет *O*(*n*)**.

### Доказательство корректности

Используем метод доказательства от противного. Предположим, что предмет *x* имеет наивысшую стоимость на единицу массы, и некоторый алгоритм находит максимальную стоимость `res`, но это решение не содержит предмет *x*.

Теперь извлечем из рюкзака единицу массы любого предмета и заменим ее единицей массы предмета *x*. Поскольку предмет *x* имеет наивысшую стоимость на единицу массы, общая стоимость после замены обязательно будет больше `res`. **Это противоречит тому, что `res` является оптимальным решением, следовательно, оптимальное решение обязательно должно содержать предмет *x***.

Для других предметов в этом решении мы также можем построить подобное противоречие. В общем, **предметы с большей стоимостью на единицу массы всегда являются более оптимальным выбором**, что доказывает эффективность жадной стратегии.

Как показано на рисунке ниже, если рассматривать массу предмета и стоимость предмета на единицу массы как горизонтальную и вертикальную оси двумерного графика соответственно, то задача о дробном рюкзаке может быть преобразована в «нахождение максимальной площади в ограниченном интервале горизонтальной оси». Эта аналогия может помочь понять эффективность жадной стратегии с геометрической точки зрения.

![Геометрическое представление задачи о дробном рюкзаке](../assets/media/image1042.jpeg)