Задача о дробном рюкзаке: жадный алгоритм с примером
Сара Чен
Что такое жадная стратегия?
Жадные алгоритмы подобны алгоритмам динамического программирования, которые часто используются для решения оптимальных задач (нахождения лучших решений задачи по определенному критерию).
Жадные алгоритмы реализуют оптимальный локальный выбор в надежде, что этот выбор приведет к оптимальному глобальному решению решаемой проблемы. Жадные алгоритмы зачастую не слишком сложны в настройке и быстры (временная сложность часто является линейной функцией или, в значительной степени, функцией второго порядка). Кроме того, эти программы не сложны в отладке и используют меньше памяти. Но результаты не всегда являются оптимальным решением.
Жадные стратегии часто используются для решения задачи комбинаторной оптимизации путем построения варианта A. Вариант A создается путем выбора каждого компонента Ai из A до тех пор, пока он не будет завершен (достаточно n компонентов). Для каждого Ai вы выбираете Ai оптимально. Таким образом, возможно, что на последнем шаге вам нечего будет выбрать, кроме как принять последнее оставшееся значение.
Есть два важнейших компонента жадных решений:
- Способ жадного отбора. Вы можете выбрать, какое решение является лучшим в данный момент, а затем решить подзадачу, возникающую в результате последнего выбора. Выбор жадных алгоритмов может зависеть от предыдущего выбора. Но оно не может зависеть от какого-либо будущего выбора или от решения подзадач. Алгоритм развивается таким образом, что выбор осуществляется в цикле, в то же время сжимая данную проблему до более мелких подзадач.
- Оптимальная подструктура. Вы выполняете оптимальную подструктуру проблемы, если оптимальное решение этой проблемы содержит оптимальные решения ее подзадач.
Жадный алгоритм состоит из пяти компонентов:
- Набор кандидатов, из которых можно создать решения.
- Функция выбора, позволяющая выбрать лучшего кандидата для добавления в решение.
- Допустимая функция используется для принятия решения о том, можно ли использовать кандидата для построения решения.
- Целевая функция, фиксирующая значение решения или неполного решения.
- Функция оценки, показывающая, когда вы найдете полное решение.
Идея жадного
С первой идеей у вас есть следующие шаги Greedy One:
- Сортировка в невозрастающем порядке значений.
- По очереди считают заказанные пакеты, укладывают рассматриваемый пакет в ранец, если оставшейся вместимости рюкзака достаточно для его вмещения (это значит, что общий вес уложенных в ранец пакетов и вес рассматриваемых пакетов не превышают вместимость рюкзака).
Однако этот жадный алгоритм не всегда дает оптимальное решение. Вот вам контрпример:
- Параметры задачи: n = 3; М = 19.
- Пакеты: {i = 1; W[i] = 14; V[i] = 20}; {я = 2; W[i] = 6; V[i] = 16}; {я = 3; W[i] = 10; В[я] = 8} -> Отличная цена, но и большой вес.
- Алгоритм выберет пакет 1 с общим значением 20, при этом выбирается оптимальное решение задачи (пакет 2, пакет 3) с общим значением 24.
Идея «Жадной двойки»
Со второй идеей у вас есть следующие шаги Greedy Two:
- Сортировка в порядке неубывания весов.
- По очереди считают заказанные пакеты, укладывают рассматриваемый пакет в ранец, если оставшейся вместимости рюкзака достаточно для его вмещения (это значит, что общий вес уложенных в ранец пакетов и вес рассматриваемых пакетов не превышают вместимость рюкзака).
Однако этот жадный алгоритм не всегда дает оптимальное решение. Вот вам контрпример:
- Параметры задачи: n = 3; М = 11.
- Пакеты: {i = 1; W[i] = 5; V[i] = 10}; {я = 2; W[i] = 6; V[i] = 16}; {я = 3; W[i] = 10; В[я] = 28} -> Легкий вес, но ценность также очень легкая.
- Алгоритм выберет (пакет 1, пакет 2) с общим значением 26, а оптимальное решение задачи — (пакет 3) с общим значением 28.
Идея «Жадной тройки»
С третьей идеей у вас есть следующие шаги Greedy Three. Фактически, это наиболее широко используемый алгоритм.
- Сортировать пакеты в порядке неувеличения значения стоимости единицы.
. У тебя есть:
- По очереди считают заказанные пакеты, укладывают рассматриваемый пакет в ранец, если оставшейся вместимости рюкзака достаточно для его вмещения (это значит, что общий вес уложенных в ранец пакетов и вес рассматриваемых пакетов не превышают вместимость рюкзака).
Идея: Жадная идея этой задачи состоит в том, чтобы вычислить 
соотношение каждого 
. Затем отсортируйте эти соотношения в порядке убывания. Вы выберете самое высокое пакет и вместимость рюкзака может вместить этот пакет (оставаться > wi). Каждый раз, когда посылка кладется в рюкзак, это также уменьшает вместимость рюкзака.
Способ выбора пакетов:
- Рассмотрим массив удельных затрат. Вы выбираете пакеты в соответствии с уменьшающейся стоимостью единицы.
- Предположим, вы нашли частичное решение: (x1,…, ИКСi).
- Стоимость рюкзака получается:
- Соответствует весу упаковок, положенных в рюкзак:
- Следовательно, остаточный предел веса рюкзака составляет:
Шаги алгоритма
Понимаете, это проблема поиска макс. Список пакетов отсортирован в порядке убывания стоимости единицы, чтобы учесть ветвление.
- Шаг 1: Корень узла представляет начальное состояние рюкзака, в котором вы не выбрали ни одного пакета.
- Общее значение = 0.
- Верхняя граница корневого узла UpperBound = M * Максимальная стоимость единицы.
- Шаг 2: Корень узла будет иметь дочерние узлы, соответствующие возможности выбора пакета с наибольшей стоимостью единицы. Для каждого узла вы пересчитываете параметры:
- TotalValue = TotalValue (старый) + количество выбранных пакетов * стоимость каждого пакета.
- M = M (старый) – количество выбранных упаковок * вес каждой посылки.
- UpperBound = TotalValue + M (новое) * Стоимость единицы упакованного продукта, который будет рассматриваться следующим.
- Шаг 3: В дочерних узлах приоритет отдается ветвлению для узла, имеющего большую верхнюю границу. Дочерние элементы этого узла соответствуют возможности выбора следующего пакета, имеющего большую стоимость единицы. Для каждого узла необходимо пересчитать параметры TotalValue, M, UpperBound по формуле, указанной в шаге 2.
- Шаг 4: Повторите шаг 3 с примечанием: для узлов, верхняя граница которых меньше или равна временной максимальной стоимости найденного варианта, вам больше не нужно разветвляться для этого узла.
- Шаг 5: Если все узлы разветвлены или обрезаны, искать самый дорогой вариант.
Псевдокод алгоритма:
Fractional Knapsack (Array W, Array V, int M) 1. for i <- 1 to size (V) 2. calculate cost[i] <- V[i] / W[i] 3. Sort-Descending (cost) 4. i ← 1 5. while (i <= size(V)) 6. if W[i] <= M 7. M ← M – W[i] 8. total ← total + V[i]; 9. if W[i] > M 10. i ← i+1
Сложность алгоритма:
- Если использовать простой алгоритм сортировки (выборочный, пузырьковый…), то сложность всей задачи составит O(n2).
- Если использовать быструю сортировку или сортировку слиянием, то сложность всей задачи составит O(nlogn).
Java код для Жадной тройки
- Сначала вы определяете класс KnapsackPackage. Этот класс имеет следующие свойства: вес, стоимость и соответствующая стоимость каждой упаковки. Стоимость свойства этого класса используется для задачи сортировки в основном алгоритме. Стоимость каждой стоимости равна
соотношение каждого пакета.
public class KnapsackPackage {
private double weight;
private double value;
private Double cost;
public KnapsackPackage(double weight, double value) {
super();
this.weight = weight;
this.value = value;
this.cost = new Double(value / weight);
}
public double getWeight() {
return weight;
}
public double getValue() {
return value;
}
public Double getCost() {
return cost;
}
}
- Затем вы создаете функцию для выполнения алгоритма Greedy Three.
public void knapsackGreProc(int W[], int V[], int M, int n) {
KnapsackPackage[] packs = new KnapsackPackage[n];
for (int i = 0; i < n; i ++) {
packs[i] = new KnapsackPackage(W[i], V[i]);
}
Arrays.sort(packs, new Comparator<KnapsackPackage>() {
@Override
public int compare(KnapsackPackage kPackA, KnapsackPackage kPackB) {
return kPackB.getCost().compareTo(kPackA.getCost());
}
});
int remain = M;
double result = 0d;
int i = 0;
boolean stopProc = false;
while (!stopProc) {
if (packs[i].getWeight() <= remain) {
remain -= packs[i].getWeight();
result += packs[i].getValue();
System.out.println("Pack " + i + " - Weight " + packs[i].getWeight() + " - Value " + packs[i].getValue());
}
if (packs[i].getWeight() > remain) {
i ++;
}
if (i == n) {
stopProc = true;
}
}
System.out.println("Max Value:\t" + result);
}
Расшифровка кода:
- Инициализируйте вес и ценность для каждого рюкзака.
- Отсортируйте рюкзаки по стоимости в порядке убывания.
- Если выбрать пакет i.
- Если выбрать количество пакетов, то мне будет достаточно.
- Остановитесь при просмотре всех пакетов.
В этом уроке у вас есть два примера. Вот Java-код для запуска вышеуказанной программы с двумя примерами:
public void run() {
/*
* Pack and Weight - Value
*/
//int W[] = new int[]{15, 10, 2, 4};
int W[] = new int[]{12, 2, 1, 1, 4};
//int V[] = new int[]{30, 25, 2, 6};
int V[] = new int[]{4, 2, 1, 2, 10};
/*
* Max Weight
*/
//int M = 37;
int M = 15;
int n = V.length;
/*
* Run the algorithm
*/
knapsackGreProc(W, V, M, n);
}
У вас есть вывод:
- Первый пример:
Pack 0 - Weight 10.0 - Value 25.0 Pack 0 - Weight 10.0 - Value 25.0 Pack 0 - Weight 10.0 - Value 25.0 Pack 2 - Weight 4.0 - Value 6.0 Pack 3 - Weight 2.0 - Value 2.0 Max Value: 83.0
- Второй пример:
Pack 0 - Weight 4.0 - Value 10.0 Pack 0 - Weight 4.0 - Value 10.0 Pack 0 - Weight 4.0 - Value 10.0 Pack 1 - Weight 1.0 - Value 2.0 Pack 1 - Weight 1.0 - Value 2.0 Pack 1 - Weight 1.0 - Value 2.0 Max Value: 36.0
Проанализируйте первый пример:
- Параметры задачи: n = 4; М = 37.
- Пакеты: {i = 1; W[i] = 15; В[и] = 30; Стоимость = 2.0}; {я = 2; W[i] = 10; В[и] = 25; Стоимость = 2.5}; {я = 3; W[i] = 2; В[я] = 4; Стоимость = 1.0}; {я = 4; W[i] = 4; В[я] = 6; Стоимость = 1.5}.
- Вы сортируете пакеты в порядке возрастания стоимости единицы. У вас есть: {я = 2} -> {я = 1} -> {я = 4} -> {я = 3}.
Шаги по применению алгоритма для первого примера:
- Определим x1, x2, x3, x4 — это номер каждого выбранного пакета, соответствующий пакету {i = 2} -> {я = 1} -> {я = 4} -> {я = 3}.
- Корень узла N представляет состояние, когда вы не выбрали ни одного пакета. Затем:
- Общее значение = 0.
- М = 37 (как предложено).
- UpperBound = 37 * 2.5 = 92.5, из которых 37 — это M, а 2.5 — стоимость единицы пакета {i = 2}.
- С пакетом {i = 2} у вас есть 4 возможности: выбрать 3 пакета {i = 2} (x1 = 3); выбрать 2 пакета {i = 2} (x1 = 2); выберите 1 пакет {i = 2} (x1 = 1) и не выбирайте пакет {i = 2} (x1 = 0). В соответствии с этими четырьмя возможностями вы разветвляете корневой узел N на 4 дочерних узла N[4], N[1], N[2] и N[3].
- Для дочернего узла N1 у вас есть:
- TotalValue = 0 + 3 * 25 = 75, где 3 — количество выбранных пакетов {i = 2}, а 25 — стоимость каждого пакета {i = 2}.
- M = 37 – 3 * 10 = 7, где 37 – начальное количество рюкзака, 3 – номер упаковки {i = 2}, 10 – вес каждой упаковки {i = 2}.
- UpperBound = 75 + 7 * 2 = 89, где 75 — TotalValue, 7 — оставшийся вес рюкзака и 2 — стоимость единицы посылки {i = 1}.
- Аналогичным образом можно вычислить параметры для узлов N[2], N[3] и N[4], в которых UpperBound равен 84, 79 и 74 соответственно.
- Среди узлов N[1], N[2], N[3] и N[4] узел N[1] имеет самую большую верхнюю границу, поэтому сначала вы разветвите узел N[1] в надежде, что появится хороший план с этого направления.
- Из узла N[1] у вас есть только один дочерний узел N[1-1], соответствующий x2 = 0 (поскольку оставшийся вес рюкзака равен 7, а вес каждого пакета {i = 1} равен 15) . После определения параметров кнопки N[1-1] верхняя граница N[1-1] равна 85.5.
- Вы продолжаете ветвление узла N[1-1]. Узел N[1-1] имеет 2 дочерних элемента N[1-1-1] и N[1-1-2], соответствующие x3 = 1 и x3 = 0. После определения параметров для этих двух узлов вы видите, что Верхняя граница N[1-1-1] равна 84, а верхняя граница N[1-1-2] равна 82, поэтому вы продолжаете ветвление узла N[1-1-1].
- Узел N[1-1-1] имеет двух дочерних узлов, N[1-1-1-1] и N[1-1-1-2], что соответствует x4 = 1 и x4 = 0. Это два листовых узла. (представляющий опцию), потому что для каждого узла было выбрано количество пакетов. В котором узел N[1-1-1-1] представляет вариант x1 = 3, x2 = 0, x3 = 1 и x4 = 1 для 83, а узел N[1-1-1-2] представляет вариант x1 = 3, x2 = 0, x3 = 1 и x4 = 01 в 81. Таким образом, временное максимальное значение здесь равно 83.
- Возвращаясь к узлу N[1-1-2], вы видите, что UpperBound N[1-1-2] равен 82 < 83, поэтому вы обрезаете узел N[1-1-2].
- Возвращаясь к узлу N2, вы видите, что верхняя граница N2 равна 84 > 83, поэтому вы продолжаете ветвление узла N2. Узел N2 имеет двух дочерних элементов N[2-1] и N[2-2], соответствующих x2 = 1 и x2 = 0. После расчета параметров для N[2-1] и N[2-2] вы увидите верхняя граница N[2-1] равна 83, а верхняя граница N[2-2] равна 75.25. Ни одно из этих значений не превышает 83, поэтому оба узла обрезаются.
- Наконец, узлы N3 и N4 также обрезаются.
- Таким образом, все узлы в дереве разветвлены или обрезаны, поэтому следует искать лучшее временное решение. Соответственно, вам необходимо выбрать 3 пакета {i = 2}, 1 пакет {i = 4} и один пакет {i = 3} общей стоимостью 83, общий вес 36.
При таком же анализе второго примера вы получите результат: выберите пакет 4 (3 раза) и пакет 5 (3 раза).
Python3 код для Жадной тройки
- Сначала вы определяете класс KnapsackPackage.
class KnapsackPackage(object):
""" Knapsack Package Data Class """
def __init__(self, weight, value):
self.weight = weight
self.value = value
self.cost = value / weight
def __lt__(self, other):
return self.cost < other.cost
- Затем вы создаете функцию для выполнения алгоритма Greedy Three.
class FractionalKnapsack(object):
def __init__(self):
def knapsackGreProc(self, W, V, M, n):
packs = []
for i in range(n):
packs.append(KnapsackPackage(W[i], V[i]))
packs.sort(reverse = True)
remain = M
result = 0
i = 0
stopProc = False
while (stopProc != True):
if (packs[i].weight <= remain):
remain -= packs[i].weight;
result += packs[i].value;
print("Pack ", i, " - Weight ", packs[i].weight, " - Value ", packs[i].value)
if (packs[i].weight > remain):
i += 1
if (i == n):
stopProc = True
print("Max Value:\t", result)
Расшифровка кода:
- Инициализируйте вес и ценность для каждого рюкзака.
- Отсортируйте рюкзаки по стоимости в порядке убывания.
- Если выбрать пакет i.
- Если выбрать количество пакетов, то мне будет достаточно.
- Остановитесь при просмотре всех пакетов.
Вот Python3 для запуска приведенной выше программы с первым примером:
if __name__ == "__main__":
W = [15, 10, 2, 4]
V = [30, 25, 2, 6]
M = 37
n = 4
proc = FractionalKnapsack()
proc.knapsackGreProc(W, V, M, n)
У вас есть вывод:
Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 2 - Weight 4 - Value 6 Pack 3 - Weight 2 - Value 2 Max Value: 83
Код C# для Greedy Three
- Сначала вы определяете класс KnapsackPackage.
using System;
namespace KnapsackProblem
{
public class KnapsackPackage
{
private double weight;
private double value;
private double cost;
public KnapsackPackage(double weight, double value)
{
this.weight = weight;
this.value = value;
this.cost = (double) value / weight;
}
public double Weight
{
get { return weight; }
}
public double Value
{
get { return value; }
}
public double Cost
{
get { return cost; }
}
}
}
- Затем вы создаете функцию для выполнения алгоритма Greedy Three.
using System;
namespace KnapsackProblem
{
public class FractionalKnapsack
{
public FractionalKnapsack()
{
}
public void KnapsackGreProc(int[] W, int[] V, int M, int n)
{
KnapsackPackage[] packs = new KnapsackPackage[n];
for (int k = 0; k < n; k++)
packs[k] = new KnapsackPackage(W[k], V[k]);
Array.Sort<KnapsackPackage>(packs, new Comparison<KnapsackPackage>(
(kPackA, kPackB) => kPackB.Cost.CompareTo(kPackA.Cost)));
double remain = M;
double result = 0d;
int i = 0;
bool stopProc = false;
while (!stopProc)
{
if (packs[i].Weight <= remain)
{
remain -= packs[i].Weight;
result += packs[i].Value;
Console.WriteLine("Pack " + i + " - Weight " + packs[i].Weight + " - Value " + packs[i].Value);
}
if (packs[i].Weight > remain)
{
i++;
}
if (i == n)
{
stopProc = true;
}
}
Console.WriteLine("Max Value:\t" + result);
}
}
}
Расшифровка кода:
- Инициализируйте вес и ценность для каждого рюкзака.
- Отсортируйте рюкзаки по стоимости в порядке убывания.
- Если выбрать пакет i.
- Если выбрать количество пакетов, то мне будет достаточно.
- Остановитесь при просмотре всех пакетов.
Вот код C# для запуска приведенной выше программы с первым примером:
public void run()
{
/*
* Pack and Weight - Value
*/
int[] W = new int[]{15, 10, 2, 4};
//int[] W = new int[] { 12, 2, 1, 1, 4 };
int[] V = new int[]{30, 25, 2, 6};
//int[] V = new int[] { 4, 2, 1, 2, 10 };
/*
* Max Weight
*/
int M = 37;
//int M = 15;
int n = V.Length;
/*
* Run the algorithm
*/
KnapsackGreProc(W, V, M, n);
}
У вас есть вывод:
Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 2 - Weight 4 - Value 6 Pack 3 - Weight 2 - Value 2 Max Value: 83
Контрпример Жадной тройки
Алгоритм Greedy Three решает быстро и в некоторых случаях может быть оптимальным. Однако в некоторых особых случаях это не дает оптимального решения. Вот вам контрпример:
- Параметры задачи: n = 3; М = 10.
- Пакеты: {i = 1; W[i] = 7; В[я] = 9; Стоимость = 9/7}; {я = 2; W[i] = 6; В[я] = 6; Стоимость = 1}; {я = 3; W[i] = 4; В[я] = 4; Стоимость = 1}.
- Алгоритм выберет (пакет 1) с общим значением 9, а оптимальное решение задачи — (пакет 2, пакет 3) с общим значением 10.
Вот Java-код для запуска указанной выше программы с противоположным примером:
public void run() {
/*
* Pack and Weight - Value
*/
int W[] = new int[]{7, 6, 4};
int V[] = new int[]{9, 6, 4};
/*
* Max Weight
*/
int M = 10;
int n = V.length;
/*
* Run the algorithm
*/
knapsackGreProc(W, V, M, n);
}
Вот результат:
Pack 0 - Weight 7.0 - Value 9.0 Max Value: 9.0
Это все, что касается задачи о дробном рюкзаке.
