Дробова проблема рюкзака: жадібний алгоритм із прикладом
Сара Чен
Що таке Greedy Strategy?
Жадібні алгоритми схожі на алгоритми динамічного програмування, які часто використовуються для вирішення оптимальних задач (знаходження найкращих розв’язків задачі за певним критерієм).
Жадібні алгоритми реалізують оптимальні локальні вибірки в надії, що ці вибірки приведуть до оптимального глобального вирішення проблеми, яку потрібно вирішити. Жадібні алгоритми часто не надто складно налаштувати, вони швидкі (часова складність часто є лінійною функцією або значною мірою функцією другого порядку). Крім того, ці програми не важко налагоджувати та займають менше пам’яті. Але результати не завжди є оптимальним рішенням.
Жадібні стратегії часто використовуються для вирішення проблеми комбінаторної оптимізації шляхом побудови варіанту A. Варіант A створюється шляхом вибору кожного компонента Ai з A до повного завершення (достатньо n компонентів). Для кожного Ai ви обираєте Ai оптимально. Таким чином, можливо, що на останньому кроці вам нічого вибрати, крім як прийняти останнє значення, що залишилося.
Є два найважливіші компоненти жадібних рішень:
- Спосіб жадібного відбору. Ви можете вибрати, яке рішення є найкращим на даний момент, а потім вирішити підпроблему, що виникає в результаті останнього вибору. Вибір жадібних алгоритмів може залежати від попереднього вибору. Але це не може залежати від будь-якого майбутнього вибору або залежно від рішень підзадач. Алгоритм розвивається таким чином, що робить вибір у циклі, водночас звужуючи дану проблему до менших підпроблем.
- Оптимальна підконструкція. Ви виконуєте оптимальну підструктуру для проблеми, якщо оптимальне рішення цієї проблеми містить оптимальні рішення її підпроблем.
Жадібний алгоритм складається з п’яти компонентів:
- Набір кандидатів, з яких можна створювати рішення.
- Функція відбору для вибору найкращого кандидата для додавання до рішення.
- Виконувана функція використовується, щоб вирішити, чи можна використовувати кандидата для створення рішення.
- Цільова функція, що фіксує значення рішення або неповного рішення.
- Функція оцінки, що вказує, коли ви знайдете повне рішення.
Ідея Greedy One
З першою ідеєю у вас є наступні кроки Greedy One:
- Сортувати в порядку незростання значень.
- По черзі враховуйте замовлені пакунки, покладіть даний пакунок у рюкзак, якщо залишилася ємність рюкзака достатня для його вмісту (це означає, що загальна вага пакунків, які були покладені в рюкзак, і вага розглянутих пакунків не перевищує місткість рюкзака).
Однак цей жадібний алгоритм не завжди дає оптимальне рішення. Ось вам і контрприклад:
- Параметри задачі: n = 3; М = 19.
- Пакети: {i = 1; W[i] = 14; V[i] = 20}; {i = 2; W[i] = 6; V[i] = 16}; {i = 3; W[i] = 10; V[i] = 8} -> Велика вартість, але також велика вага.
- Алгоритм вибере пакет 1 із загальним значенням 20, а оптимальний розв’язок задачі вибере (пакет 2, пакет 3) із загальним значенням 24.
Ідея Greedy Two
З другою ідеєю у вас є наступні кроки Greedy Two:
- Сортувати в порядку неубування ваг.
- По черзі враховуйте замовлені пакунки, покладіть даний пакунок у рюкзак, якщо залишилася ємність рюкзака достатня для його вмісту (це означає, що загальна вага пакунків, які були покладені в рюкзак, і вага розглянутих пакунків не перевищує місткість рюкзака).
Однак цей жадібний алгоритм не завжди дає оптимальне рішення. Ось вам і контрприклад:
- Параметри задачі: n = 3; М = 11.
- Пакети: {i = 1; W[i] = 5; V[i] = 10}; {i = 2; W[i] = 6; V[i] = 16}; {i = 3; W[i] = 10; V[i] = 28} -> Невелика вага, але вартість також дуже мала.
- Алгоритм вибере (пакет 1, пакет 2) із загальним значенням 26, а оптимальним розв’язком задачі є (пакет 3) із загальним значенням 28.
Ідея Greedy Three
З третьою ідеєю у вас є наступні кроки Greedy Three. Фактично, це найпоширеніший алгоритм.
- Розсортуйте пакети в порядку незростання вартості одиниці товару
. Ти маєш:
- По черзі враховуйте замовлені пакунки, покладіть даний пакунок у рюкзак, якщо залишилася ємність рюкзака достатня для його вмісту (це означає, що загальна вага пакунків, які були покладені в рюкзак, і вага розглянутих пакунків не перевищує місткість рюкзака).
Ідея: Жадібна ідея цієї проблеми полягає в тому, щоб обчислити 
співвідношення кожного 
. Потім відсортуйте ці співвідношення в порядку спадання. Ви виберете найвищий пакет і місткість рюкзака може вмістити цей пакет (remain > wi). Кожного разу, коли пакет кладуть у рюкзак, це також зменшує місткість рюкзака.
Спосіб вибору пакетів:
- Розглянемо масив одиничних витрат. Ви обираєте пакети відповідно до зменшення одиничних витрат.
- Припустимо, ви знайшли часткове рішення: (x1,…, Xi).
- Значення рюкзака виходить:
- Відповідає вазі пакунків, які були покладені в рюкзак:
- Таким чином, залишкова вага ранця становить:
Кроки алгоритму
Ви бачите, що це проблема пошуку макс. Список пакетів відсортовано в порядку спадання вартості одиниці, щоб розглянути розгалуження.
- крок 1: Корінь вузла представляє початковий стан рюкзака, де ви не вибрали жодного пакета.
- TotalValue = 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 код для Greedy Three
- По-перше, ви визначаєте клас 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.
- Якщо вибрати кількість пакетів 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; V[i] = 30; Вартість = 2.0}; {i = 2; W[i] = 10; V[i] = 25; Вартість = 2.5}; {i = 3; W[i] = 2; V[i] = 4; Вартість = 1.0}; {i = 4; W[i] = 4; V[i] = 6; Вартість = 1.5}.
- Ви сортуєте пакети в порядку відсутності збільшення вартості одиниці товару. У вас є: {i = 2} -> {i = 1} -> {i = 4} -> {i = 3}.
Етапи застосування алгоритму для першого прикладу:
- Визначте, що x1, x2, x3, x4 є номером кожного вибраного пакета, що відповідає пакету {i = 2} -> {i = 1} -> {i = 4} -> {i = 3}.
- Корінь вузла N представляє стан, що ви не вибрали жодного пакета. Потім:
- TotalValue = 0.
- M = 37 (як запропоновано).
- Верхня межа = 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). Відповідно до цих 4 можливостей ви розгалужуєте кореневий вузол N до 4 дочірніх вузлів N[1], N[2], N[3] і N[4].
- Для дочірнього вузла 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], у яких верхня межа становить 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], ви побачите, що верхня межа 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 код для Greedy Three
- По-перше, ви визначаєте клас 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.
- Якщо вибрати кількість пакетів 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.
- Якщо вибрати кількість пакетів 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
Алгоритм Greedy Three вирішується швидко і також може бути оптимальним у деяких випадках. Однак у деяких особливих випадках це не дає оптимального рішення. Ось вам і контрприклад:
- Параметри задачі: n = 3; М = 10.
- Пакети: {i = 1; W[i] = 7; V[i] = 9; Вартість = 9/7}; {i = 2; W[i] = 6; V[i] = 6; Вартість = 1}; {i = 3; W[i] = 4; V[i] = 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
Це все, що стосується проблеми дробового ранця.
