15.2 Задача о дробном рюкзаке¶
Question
Дано \(n\) предметов. Вес предмета \(i\) равен \(wgt[i-1]\), ценность равна \(val[i-1]\), также дан рюкзак вместимостью \(cap\). Каждый предмет можно выбрать только один раз, но разрешается взять лишь часть предмета, а ценность вычисляется пропорционально взятому весу. Требуется найти максимальную ценность предметов в рюкзаке при ограниченной вместимости. Пример показан на рисунке 15-3.
Рисунок 15-3 Пример данных для задачи о дробном рюкзаке
Задача о дробном рюкзаке в целом очень похожа на задачу о рюкзаке 0-1: состояние включает текущий предмет \(i\) и вместимость \(c\), а цель состоит в нахождении максимальной ценности при заданной вместимости рюкзака.
Отличие в том, что здесь разрешено брать только часть предмета. Как показано на рисунке 15-4, мы можем произвольно делить предмет и вычислять соответствующую ценность пропорционально весу.
- Для предмета \(i\) его ценность на единицу веса равна \(val[i-1] / wgt[i-1]\), сокращенно - удельная ценность.
- Если взять часть предмета \(i\) весом \(w\), то ценность рюкзака увеличится на \(w \times val[i-1] / wgt[i-1]\).
Рисунок 15-4 Ценность предмета на единицу веса
1. Определение жадной стратегии¶
Максимизация общей ценности предметов в рюкзаке по сути равносильна максимизации ценности на единицу веса. Отсюда естественно выводится следующая жадная стратегия.
- Отсортировать предметы по убыванию удельной ценности.
- Перебирать все предметы и на каждом шаге жадно выбирать предмет с наибольшей удельной ценностью.
- Если оставшейся вместимости рюкзака недостаточно, взять часть текущего предмета, чтобы заполнить рюкзак.
Рисунок 15-5 Жадная стратегия для задачи о дробном рюкзаке
2. Код реализации¶
Мы вводим класс Item, чтобы можно было сортировать предметы по удельной ценности. Далее циклически выполняем жадный выбор и, когда рюкзак заполнен, выходим и возвращаем ответ:
fractional_knapsack.py
class Item:
"""Предмет"""
def __init__(self, w: int, v: int):
self.w = w # Вес предмета
self.v = v # Стоимость предмета
def fractional_knapsack(wgt: list[int], val: list[int], cap: int) -> int:
"""Дробный рюкзак: жадный алгоритм"""
# Создать список предметов с двумя свойствами: вес и стоимость
items = [Item(w, v) for w, v in zip(wgt, val)]
# Отсортировать по удельной стоимости item.v / item.w в порядке убывания
items.sort(key=lambda item: item.v / item.w, reverse=True)
# Циклический жадный выбор
res = 0
for item in items:
if item.w <= cap:
# Если оставшейся вместимости достаточно, положить в рюкзак текущий предмет целиком
res += item.v
cap -= item.w
else:
# Если оставшейся вместимости недостаточно, положить в рюкзак часть текущего предмета
res += (item.v / item.w) * cap
# Свободной вместимости больше не осталось, поэтому выйти из цикла
break
return res
fractional_knapsack.cpp
/* Предмет */
class Item {
public:
int w; // Вес предмета
int v; // Стоимость предмета
Item(int w, int v) : w(w), v(v) {
}
};
/* Дробный рюкзак: жадный алгоритм */
double fractionalKnapsack(vector<int> &wgt, vector<int> &val, int cap) {
// Создать список предметов с двумя свойствами: вес и стоимость
vector<Item> items;
for (int i = 0; i < wgt.size(); i++) {
items.push_back(Item(wgt[i], val[i]));
}
// Отсортировать по удельной стоимости item.v / item.w в порядке убывания
sort(items.begin(), items.end(), [](Item &a, Item &b) { return (double)a.v / a.w > (double)b.v / b.w; });
// Циклический жадный выбор
double res = 0;
for (auto &item : items) {
if (item.w <= cap) {
// Если оставшейся вместимости достаточно, положить в рюкзак текущий предмет целиком
res += item.v;
cap -= item.w;
} else {
// Если оставшейся вместимости недостаточно, положить в рюкзак часть текущего предмета
res += (double)item.v / item.w * cap;
// Свободной вместимости больше не осталось, поэтому выйти из цикла
break;
}
}
return res;
}
fractional_knapsack.java
/* Предмет */
class Item {
int w; // Вес предмета
int v; // Стоимость предмета
public Item(int w, int v) {
this.w = w;
this.v = v;
}
}
/* Дробный рюкзак: жадный алгоритм */
double fractionalKnapsack(int[] wgt, int[] val, int cap) {
// Создать список предметов с двумя свойствами: вес и стоимость
Item[] items = new Item[wgt.length];
for (int i = 0; i < wgt.length; i++) {
items[i] = new Item(wgt[i], val[i]);
}
// Отсортировать по удельной стоимости item.v / item.w в порядке убывания
Arrays.sort(items, Comparator.comparingDouble(item -> -((double) item.v / item.w)));
// Циклический жадный выбор
double res = 0;
for (Item item : items) {
if (item.w <= cap) {
// Если оставшейся вместимости достаточно, положить в рюкзак текущий предмет целиком
res += item.v;
cap -= item.w;
} else {
// Если оставшейся вместимости недостаточно, положить в рюкзак часть текущего предмета
res += (double) item.v / item.w * cap;
// Свободной вместимости больше не осталось, поэтому выйти из цикла
break;
}
}
return res;
}
fractional_knapsack.cs
/* Предмет */
class Item(int w, int v) {
public int w = w; // Вес предмета
public int v = v; // Стоимость предмета
}
/* Дробный рюкзак: жадный алгоритм */
double FractionalKnapsack(int[] wgt, int[] val, int cap) {
// Создать список предметов с двумя свойствами: вес и стоимость
Item[] items = new Item[wgt.Length];
for (int i = 0; i < wgt.Length; i++) {
items[i] = new Item(wgt[i], val[i]);
}
// Отсортировать по удельной стоимости item.v / item.w в порядке убывания
Array.Sort(items, (x, y) => (y.v / y.w).CompareTo(x.v / x.w));
// Циклический жадный выбор
double res = 0;
foreach (Item item in items) {
if (item.w <= cap) {
// Если оставшейся вместимости достаточно, положить в рюкзак текущий предмет целиком
res += item.v;
cap -= item.w;
} else {
// Если оставшейся вместимости недостаточно, положить в рюкзак часть текущего предмета
res += (double)item.v / item.w * cap;
// Свободной вместимости больше не осталось, поэтому выйти из цикла
break;
}
}
return res;
}
fractional_knapsack.go
/* Предмет */
type Item struct {
w int // Вес предмета
v int // Стоимость предмета
}
/* Дробный рюкзак: жадный алгоритм */
func fractionalKnapsack(wgt []int, val []int, cap int) float64 {
// Создать список предметов с двумя свойствами: вес и стоимость
items := make([]Item, len(wgt))
for i := 0; i < len(wgt); i++ {
items[i] = Item{wgt[i], val[i]}
}
// Отсортировать по удельной стоимости item.v / item.w в порядке убывания
sort.Slice(items, func(i, j int) bool {
return float64(items[i].v)/float64(items[i].w) > float64(items[j].v)/float64(items[j].w)
})
// Циклический жадный выбор
res := 0.0
for _, item := range items {
if item.w <= cap {
// Если оставшейся вместимости достаточно, положить в рюкзак текущий предмет целиком
res += float64(item.v)
cap -= item.w
} else {
// Если оставшейся вместимости недостаточно, положить в рюкзак часть текущего предмета
res += float64(item.v) / float64(item.w) * float64(cap)
// Свободной вместимости больше не осталось, поэтому выйти из цикла
break
}
}
return res
}
fractional_knapsack.swift
/* Предмет */
class Item {
var w: Int // Вес предмета
var v: Int // Стоимость предмета
init(w: Int, v: Int) {
self.w = w
self.v = v
}
}
/* Дробный рюкзак: жадный алгоритм */
func fractionalKnapsack(wgt: [Int], val: [Int], cap: Int) -> Double {
// Создать список предметов с двумя свойствами: вес и стоимость
var items = zip(wgt, val).map { Item(w: $0, v: $1) }
// Отсортировать по удельной стоимости item.v / item.w в порядке убывания
items.sort { -(Double($0.v) / Double($0.w)) < -(Double($1.v) / Double($1.w)) }
// Циклический жадный выбор
var res = 0.0
var cap = cap
for item in items {
if item.w <= cap {
// Если оставшейся вместимости достаточно, положить в рюкзак текущий предмет целиком
res += Double(item.v)
cap -= item.w
} else {
// Если оставшейся вместимости недостаточно, положить в рюкзак часть текущего предмета
res += Double(item.v) / Double(item.w) * Double(cap)
// Свободной вместимости больше не осталось, поэтому выйти из цикла
break
}
}
return res
}
fractional_knapsack.js
/* Предмет */
class Item {
constructor(w, v) {
this.w = w; // Вес предмета
this.v = v; // Стоимость предмета
}
}
/* Дробный рюкзак: жадный алгоритм */
function fractionalKnapsack(wgt, val, cap) {
// Создать список предметов с двумя свойствами: вес и стоимость
const items = wgt.map((w, i) => new Item(w, val[i]));
// Отсортировать по удельной стоимости item.v / item.w в порядке убывания
items.sort((a, b) => b.v / b.w - a.v / a.w);
// Циклический жадный выбор
let res = 0;
for (const item of items) {
if (item.w <= cap) {
// Если оставшейся вместимости достаточно, положить в рюкзак текущий предмет целиком
res += item.v;
cap -= item.w;
} else {
// Если оставшейся вместимости недостаточно, положить в рюкзак часть текущего предмета
res += (item.v / item.w) * cap;
// Свободной вместимости больше не осталось, поэтому выйти из цикла
break;
}
}
return res;
}
fractional_knapsack.ts
/* Предмет */
class Item {
w: number; // Вес предмета
v: number; // Стоимость предмета
constructor(w: number, v: number) {
this.w = w;
this.v = v;
}
}
/* Дробный рюкзак: жадный алгоритм */
function fractionalKnapsack(wgt: number[], val: number[], cap: number): number {
// Создать список предметов с двумя свойствами: вес и стоимость
const items: Item[] = wgt.map((w, i) => new Item(w, val[i]));
// Отсортировать по удельной стоимости item.v / item.w в порядке убывания
items.sort((a, b) => b.v / b.w - a.v / a.w);
// Циклический жадный выбор
let res = 0;
for (const item of items) {
if (item.w <= cap) {
// Если оставшейся вместимости достаточно, положить в рюкзак текущий предмет целиком
res += item.v;
cap -= item.w;
} else {
// Если оставшейся вместимости недостаточно, положить в рюкзак часть текущего предмета
res += (item.v / item.w) * cap;
// Свободной вместимости больше не осталось, поэтому выйти из цикла
break;
}
}
return res;
}
fractional_knapsack.dart
/* Предмет */
class Item {
int w; // Вес предмета
int v; // Стоимость предмета
Item(this.w, this.v);
}
/* Дробный рюкзак: жадный алгоритм */
double fractionalKnapsack(List<int> wgt, List<int> val, int cap) {
// Создать список предметов с двумя свойствами: вес и стоимость
List<Item> items = List.generate(wgt.length, (i) => Item(wgt[i], val[i]));
// Отсортировать по удельной стоимости item.v / item.w в порядке убывания
items.sort((a, b) => (b.v / b.w).compareTo(a.v / a.w));
// Циклический жадный выбор
double res = 0;
for (Item item in items) {
if (item.w <= cap) {
// Если оставшейся вместимости достаточно, положить в рюкзак текущий предмет целиком
res += item.v;
cap -= item.w;
} else {
// Если оставшейся вместимости недостаточно, положить в рюкзак часть текущего предмета
res += item.v / item.w * cap;
// Свободной вместимости больше не осталось, поэтому выйти из цикла
break;
}
}
return res;
}
fractional_knapsack.rs
/* Предмет */
struct Item {
w: i32, // Вес предмета
v: i32, // Стоимость предмета
}
impl Item {
fn new(w: i32, v: i32) -> Self {
Self { w, v }
}
}
/* Дробный рюкзак: жадный алгоритм */
fn fractional_knapsack(wgt: &[i32], val: &[i32], mut cap: i32) -> f64 {
// Создать список предметов с двумя свойствами: вес и стоимость
let mut items = wgt
.iter()
.zip(val.iter())
.map(|(&w, &v)| Item::new(w, v))
.collect::<Vec<Item>>();
// Отсортировать по удельной стоимости item.v / item.w в порядке убывания
items.sort_by(|a, b| {
(b.v as f64 / b.w as f64)
.partial_cmp(&(a.v as f64 / a.w as f64))
.unwrap()
});
// Циклический жадный выбор
let mut res = 0.0;
for item in &items {
if item.w <= cap {
// Если оставшейся вместимости достаточно, положить в рюкзак текущий предмет целиком
res += item.v as f64;
cap -= item.w;
} else {
// Если оставшейся вместимости недостаточно, положить в рюкзак часть текущего предмета
res += item.v as f64 / item.w as f64 * cap as f64;
// Свободной вместимости больше не осталось, поэтому выйти из цикла
break;
}
}
res
}
fractional_knapsack.c
/* Предмет */
typedef struct {
int w; // Вес предмета
int v; // Стоимость предмета
} Item;
/* Дробный рюкзак: жадный алгоритм */
float fractionalKnapsack(int wgt[], int val[], int itemCount, int cap) {
// Создать список предметов с двумя свойствами: вес и стоимость
Item *items = malloc(sizeof(Item) * itemCount);
for (int i = 0; i < itemCount; i++) {
items[i] = (Item){.w = wgt[i], .v = val[i]};
}
// Отсортировать по удельной стоимости item.v / item.w в порядке убывания
qsort(items, (size_t)itemCount, sizeof(Item), sortByValueDensity);
// Циклический жадный выбор
float res = 0.0;
for (int i = 0; i < itemCount; i++) {
if (items[i].w <= cap) {
// Если оставшейся вместимости достаточно, положить в рюкзак текущий предмет целиком
res += items[i].v;
cap -= items[i].w;
} else {
// Если оставшейся вместимости недостаточно, положить в рюкзак часть текущего предмета
res += (float)cap / items[i].w * items[i].v;
cap = 0;
break;
}
}
free(items);
return res;
}
fractional_knapsack.kt
/* Предмет */
class Item(
val w: Int, // Предмет
val v: Int // Стоимость предмета
)
/* Дробный рюкзак: жадный алгоритм */
fun fractionalKnapsack(wgt: IntArray, _val: IntArray, c: Int): Double {
// Создать список предметов с двумя свойствами: вес и стоимость
var cap = c
val items = arrayOfNulls<Item>(wgt.size)
for (i in wgt.indices) {
items[i] = Item(wgt[i], _val[i])
}
// Отсортировать по удельной стоимости item.v / item.w в порядке убывания
items.sortBy { item: Item? -> -(item!!.v.toDouble() / item.w) }
// Циклический жадный выбор
var res = 0.0
for (item in items) {
if (item!!.w <= cap) {
// Если оставшейся вместимости достаточно, положить в рюкзак текущий предмет целиком
res += item.v
cap -= item.w
} else {
// Если оставшейся вместимости недостаточно, положить в рюкзак часть текущего предмета
res += item.v.toDouble() / item.w * cap
// Свободной вместимости больше не осталось, поэтому выйти из цикла
break
}
}
return res
}
fractional_knapsack.rb
### Предмет ###
class Item
attr_accessor :w # Вес предмета
attr_accessor :v # Стоимость предмета
def initialize(w, v)
@w = w
@v = v
end
end
### Дробный рюкзак: жадный алгоритм ###
def fractional_knapsack(wgt, val, cap)
# Создать список предметов с двумя свойствами: вес и стоимость
items = wgt.each_with_index.map { |w, i| Item.new(w, val[i]) }
# Отсортировать по удельной стоимости item.v / item.w в порядке убывания
items.sort! { |a, b| (b.v.to_f / b.w) <=> (a.v.to_f / a.w) }
# Циклический жадный выбор
res = 0
for item in items
if item.w <= cap
# Если оставшейся вместимости достаточно, положить в рюкзак текущий предмет целиком
res += item.v
cap -= item.w
else
# Если оставшейся вместимости недостаточно, положить в рюкзак часть текущего предмета
res += (item.v.to_f / item.w) * cap
# Свободной вместимости больше не осталось, поэтому выйти из цикла
break
end
end
res
end
Визуализация кода
Встроенный алгоритм сортировки обычно имеет временную сложность \(O(\log n)\), а пространственная сложность обычно равна \(O(\log n)\) или \(O(n)\), в зависимости от конкретной реализации в языке программирования.
Помимо сортировки, в худшем случае потребуется пройти весь список предметов, поэтому временная сложность равна \(O(n)\), где \(n\) - число предметов.
Поскольку инициализируется список объектов Item, пространственная сложность равна \(O(n)\).
3. Доказательство корректности¶
Используем доказательство от противного. Предположим, что предмет \(x\) имеет наибольшую удельную ценность, некоторый алгоритм получил максимальную ценность res, но в найденном решении предмет \(x\) отсутствует.
Теперь вынем из рюкзака произвольный предмет единичного веса и заменим его на предмет \(x\) того же веса. Поскольку предмет \(x\) имеет наибольшую удельную ценность, общая ценность после замены обязательно станет больше res. Это противоречит тому, что res является оптимальным решением, а значит оптимальное решение обязательно содержит предмет \(x\).
Для других предметов в этом решении можно построить аналогичное противоречие. Иными словами, предметы с большей удельной ценностью всегда являются более выгодным выбором, а значит жадная стратегия корректна.
Как показано на рисунке 15-6, если рассматривать вес предметов и их удельную ценность как горизонтальную и вертикальную оси двумерной диаграммы, то задачу о дробном рюкзаке можно интерпретировать как «поиск максимальной площади, ограниченной конечным отрезком по горизонтали». Эта аналогия помогает понять корректность жадной стратегии с геометрической точки зрения.
Рисунок 15-6 Геометрическая интерпретация задачи о дробном рюкзаке