mirror of
https://github.com/krahets/hello-algo.git
synced 2026-07-07 21:24:18 +00:00
Yudong Jin
22b3b568ef
* docs(ru): replace prose quotes with guillemets * docs(ru): replace prose semicolons with periods * docs(ru): align animation title forms * docs(ru): align figure and table references
53 lines
6.6 KiB
Markdown
53 lines
6.6 KiB
Markdown
# Задача о дробном рюкзаке
|
|
|
|
!!! question
|
|
|
|
Дано $n$ предметов. Вес предмета $i$ равен $wgt[i-1]$, ценность равна $val[i-1]$, также дан рюкзак вместимостью $cap$. Каждый предмет можно выбрать только один раз, **но разрешается взять лишь часть предмета, а ценность вычисляется пропорционально взятому весу**. Требуется найти максимальную ценность предметов в рюкзаке при ограниченной вместимости. Пример показан на рисунке ниже.
|
|
|
|
|
|
|
|
Задача о дробном рюкзаке в целом очень похожа на задачу о рюкзаке 0-1: состояние включает текущий предмет $i$ и вместимость $c$, а цель состоит в нахождении максимальной ценности при заданной вместимости рюкзака.
|
|
|
|
Отличие в том, что здесь разрешено брать только часть предмета. Как показано на рисунке ниже, **мы можем произвольно делить предмет и вычислять соответствующую ценность пропорционально весу**.
|
|
|
|
1. Для предмета $i$ его ценность на единицу веса равна $val[i-1] / wgt[i-1]$, сокращенно - удельная ценность.
|
|
2. Если взять часть предмета $i$ весом $w$, то ценность рюкзака увеличится на $w \times val[i-1] / wgt[i-1]$.
|
|
|
|
|
|
|
|
### Определение жадной стратегии
|
|
|
|
Максимизация общей ценности предметов в рюкзаке **по сути равносильна максимизации ценности на единицу веса**. Отсюда естественно выводится жадная стратегия, показанная на рисунке ниже.
|
|
|
|
1. Отсортировать предметы по убыванию удельной ценности.
|
|
2. Перебирать все предметы и **на каждом шаге жадно выбирать предмет с наибольшей удельной ценностью**.
|
|
3. Если оставшейся вместимости рюкзака недостаточно, взять часть текущего предмета, чтобы заполнить рюкзак.
|
|
|
|
|
|
|
|
### Код реализации
|
|
|
|
Мы вводим класс `Item`, чтобы можно было сортировать предметы по удельной ценности. Далее циклически выполняем жадный выбор и, когда рюкзак заполнен, выходим и возвращаем ответ:
|
|
|
|
```src
|
|
[file]{fractional_knapsack}-[class]{}-[func]{fractional_knapsack}
|
|
```
|
|
|
|
Встроенный алгоритм сортировки обычно имеет временную сложность $O(n \log n)$, а пространственная сложность обычно равна $O(\log n)$ или $O(n)$, в зависимости от конкретной реализации в языке программирования.
|
|
|
|
Помимо сортировки, в худшем случае потребуется пройти весь список предметов, но это не меняет асимптотику, **поэтому итоговая временная сложность равна $O(n \log n)$**, где $n$ - число предметов.
|
|
|
|
Поскольку инициализируется список объектов `Item`, **пространственная сложность равна $O(n)$**.
|
|
|
|
### Доказательство корректности
|
|
|
|
Используем доказательство от противного. Предположим, что предмет $x$ имеет наибольшую удельную ценность, некоторый алгоритм получил максимальную ценность `res`, но в найденном решении предмет $x$ отсутствует.
|
|
|
|
Теперь вынем из рюкзака произвольный предмет единичного веса и заменим его на предмет $x$ того же веса. Поскольку предмет $x$ имеет наибольшую удельную ценность, общая ценность после замены обязательно станет больше `res`. **Это противоречит тому, что `res` является оптимальным решением, а значит оптимальное решение обязательно содержит предмет $x$**.
|
|
|
|
Для других предметов в этом решении можно построить аналогичное противоречие. Иными словами, **предметы с большей удельной ценностью всегда являются более выгодным выбором**, а значит жадная стратегия корректна.
|
|
|
|
Как показано на рисунке ниже, если рассматривать вес предметов и их удельную ценность как горизонтальную и вертикальную оси двумерной диаграммы, то задачу о дробном рюкзаке можно интерпретировать как «поиск максимальной площади, ограниченной конечным отрезком по горизонтали». Эта аналогия помогает понять корректность жадной стратегии с геометрической точки зрения.
|
|
|
|
|