krahets
6.8 KiB
Задача о дробном рюкзаке
!!! question
Дано *n* предметов, где *i*-й предмет имеет массу *wgt*[*i*-1] и стоимость *val*[*i*-1], и рюкзак вместимостью *cap*. Каждый предмет можно выбрать только один раз, **но можно выбрать часть предмета, при этом стоимость рассчитывается пропорционально выбранной массе**. Требуется найти максимальную стоимость предметов в рюкзаке при ограниченной вместимости. Пример показан на рисунке ниже.
Задача о дробном рюкзаке и задача о рюкзаке 0-1 в целом очень похожи: состояние включает текущий предмет i и вместимость c, цель -- найти максимальную стоимость при ограниченной вместимости рюкзака.
Отличие в том, что в данной задаче допускается выбирать часть предмета. Как показано на рисунке ниже, можно произвольно разделять предметы и рассчитывать соответствующую стоимость пропорционально массе.
- Для предмета i его стоимость на единицу массы равна val[i - 1]/wgt[i - 1], сокращенно -- удельная стоимость.
- Предположим, что в рюкзак помещена часть предмета i массой w, тогда увеличение стоимости рюкзака составит w × val[i - 1]/wgt[i - 1].
Определение жадной стратегии
Максимизация общей стоимости предметов в рюкзаке, по сути, является максимизацией стоимости предметов на единицу массы. Из этого можно вывести жадную стратегию, изображенную на рисунке ниже.
- Отсортировать предметы по убыванию стоимости на единицу массы.
- Перебирать все предметы и жадно выбирать на каждом этапе предмет с наивысшей стоимостью на единицу массы.
- Если оставшейся вместимости рюкзака недостаточно, использовать часть текущего предмета для заполнения рюкзака.
Реализация кода
Мы создали класс предмета Item для сортировки предметов по стоимости на единицу массы. Выполняем цикл жадного выбора, прерываем его и возвращаем решение, когда рюкзак заполнен:
[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.
Для других предметов в этом решении мы также можем построить подобное противоречие. В общем, предметы с большей стоимостью на единицу массы всегда являются более оптимальным выбором, что доказывает эффективность жадной стратегии.
Как показано на рисунке ниже, если рассматривать массу предмета и стоимость предмета на единицу массы как горизонтальную и вертикальную оси двумерного графика соответственно, то задача о дробном рюкзаке может быть преобразована в «нахождение максимальной площади в ограниченном интервале горизонтальной оси». Эта аналогия может помочь понять эффективность жадной стратегии с геометрической точки зрения.