Дробова проблема рюкзака: жадібний алгоритм із прикладом

Що таке Greedy Strategy?

Жадібні алгоритми вибирати найкращий локальний варіант на кожному кроці в надії, що ланцюг локальних оптимумів призведе до глобально оптимального рішення. Як і динамічне програмування, вони спрямовані на проблеми оптимізації, але ніколи не озираються назад, щоб переглянути попередні рішення.

Жадібні алгоритми зазвичай прості в написанні, швидкі (часто лінійні або квадратичні за часом), легко налагоджуються та потребують мало пам'яті. Компроміс полягає в тому, що результат не завжди оптимальний, тому ця стратегія працює лише для задач, які мають перевірену жадібно-безпечну структуру.

Жадібні стратегії вирішують комбінаторну оптимізацію, будуючи рішення A з одним компонентом Ai за раз. На кожному кроці ви вибираєте Ai оптимально за поточних обмежень та зменшуєте проблему до меншої підзадачі.

Для коректності жадібного методу повинні виконуватися дві властивості:

1. Властивість жадібного вибору: Локальний оптимум на кожному кроці призводить до глобального оптимуму. Вибір залежить від минулих рішень, але не від майбутніх.
2. Оптимальна підструктура: Оптимальне рішення всієї задачі містить оптимальні рішення її підзадач.

Жадібний алгоритм складається з п’яти компонентів:

1. Набір кандидатів, з якого будуються рішення.
2. Функція вибору, яка вибирає найкращого наступного кандидата.
3. Функція доцільності, яка перевіряє, чи може кандидат розширити поточне часткове рішення.
4. Цільова функція, яка оцінює повне або часткове рішення.
5. Функція оцінювання, яка сигналізує про завершення розв'язку.

Ідея Greedy One

Greedy One сортує пакети лише за вартістю:

• Сортувати посилки не за зростанням вартості.
• Пройдіться відсортованим списком і додайте кожен пакет до рюкзака, якщо його достатньо.

Це правило не завжди дає оптимальну відповідь. Контрприклад:

• Параметри: n = 3, M = 19.
• Пакети: {i = 1; W = 14; V = 20}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 8} — висока цінність, але також і велика вага.
• Жадібний вибирає пакет 1 із загальним значенням 20, тоді як оптимальний вибір (пакет 2, пакет 3) досягає 24.

Ідея Greedy Two

Жадібні два види упаковок лише за вагою:

• Сортуйте посилки в неспадному порядку за вагою.
• Пройдіться відсортованим списком і додайте кожен пакет до рюкзака, якщо його достатньо.

Це правило також не є оптимальним. Контрприклад:

• Параметри: n = 3, M = 11.
• Пакети: {i = 1; W = 5; V = 10}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 28} — легкі, але низька вартість.
• Жадібний вибір. Два варіанти (пакет 1, пакет 2) із загальним значенням 26, тоді як оптимальний вибір (пакет 3) досягає 28.

Ідея Greedy Three

Метод «Жадібна трійка» виправляє обидві невдачі, об'єднуючи значення та вагу в один ключ ранжування. Це стандартний метод для задачі дробового рюкзака.

• Обчисліть собівартість одиниці V[i] / W[i] для кожного пакета.
• Сортуйте упаковки в порядку зростання вартості одиниці.
• Пройдіться відсортованим списком і додайте кожен пакет, якщо його достатньо для розміщення.

Жадібні три сорти за вартістю одиниці V[i] / W[i]

Ідея: Обчисліть співвідношення вартості до ваги V[i] / W[i] для кожного пакунка, відсортуйте у порядку спадання та візьміть спочатку найбільше доступне співвідношення, поки рюкзак не заповниться.

Для справжнього Дробний варіант, коли наступний пакет не може поміститися цілим, візьміть дріб, який точно заповнює решту місткості. Це додаткове правило робить Greedy Three доведено оптимальним на Fractional Knapsack.

Кроки алгоритму

Для варіанту 0/1 з гілками та межами відсортований список собівартості одиниці керує деревом пошуку:

• Крок 1: Кореневий вузол представляє порожній рюкзак. TotalValue = 0. UpperBound = M × максимальна вартість одиниці.
• Крок 2: Розгалужується корінь за кількістю копій пакета з найбільшим співвідношенням, що може поміститися. Для кожного дочірнього елемента переобчисліть ЗагальнеЗначення (TotalValue), залишок ємності M та ВерхнюМежу (UpperBound).
• Крок 3: Спочатку розгорніть дочірній об'єкт з найбільшим значенням UpperBound, сподіваючись швидко знайти сильне рішення.
• Крок 4: Видаліть будь-який вузол, верхня межа якого не краща за поточний найкращий повний розв'язок.
• Крок 5: Коли кожен вузол або розширюється, або обрізається, поточний найкращий повний розв'язок є оптимальним.

Псевдокод для чистого жадібного алгоритму дробового рюкзака:

Fractional Knapsack (Array W, Array V, int M)
1. for i <- 1 to size(V)
2.     cost[i] <- V[i] / W[i]
3. Sort-Descending(cost)
4. total <- 0
5. i <- 1
6. while (i <= size(V) and M > 0)
7.     if W[i] <= M
8.         M <- M - W[i]
9.         total <- total + V[i]
10.        i <- i + 1
11.    else
12.        total <- total + V[i] * (M / W[i])
13.        M <- 0

Складність алгоритму:

• Використання простого сортування (вибір або бульбашка): O(n²).
• Використання швидкого сортування або сортування злиттям: O(n log n), де домінує крок сортування.

Java Code для Жадібної Трійки

Визначте KnapsackPackage клас з вагою, вартістю та похідною вартістю (співвідношення V/W, що використовується для сортування):

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 = Double.valueOf(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 a, KnapsackPackage b) {
            return b.getCost().compareTo(a.getCost());
        }
    });

    double remain = M;
    double result = 0d;

    for (int i = 0; i < n && remain > 0; i++) {
        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());
        } else {
            double fraction = remain / packs[i].getWeight();
            result += packs[i].getValue() * fraction;
            System.out.println("Pack " + i + " - Fraction " + fraction
                             + " - Value " + packs[i].getValue() * fraction);
            remain = 0;
        }
    }

    System.out.println("Max Value:\t" + result);
}

Функція napsackGreProc() в Java

Пояснення коду:

1. Оберніть кожен вхідний сигнал у KnapsackPackage таким чином, ключ сортування (співвідношення V/W) попередньо обчислюється.
2. Сортувати у порядку спадання вартості.
3. Візьміть кожну упаковку цілою, якщо вона підходить.
4. Візьміть частину наступної упаковки, щоб заповнити місткість, що залишилася.
5. Зупиніться, як тільки залишкова ємність досягне нуля.

Виправлення примітки: оригінальні Java цикл розширений i лише тоді, коли пакет не поміщався, що призводило до повторного використання того самого пакету. У версії вище просувається на один пакет за ітерацію та додає крок дробового заповнення, що відповідає справжньому правилу дробового рюкзака.

Java драйвер, який запускає алгоритм на робочому прикладі:

public void run() {
    int W[] = new int[]{15, 10, 2, 4};
    int V[] = new int[]{30, 25, 2, 6};
    int M = 37;
    int n = V.length;
    knapsackGreProc(W, V, M, n);
}

Python3 Code для Жадібної Трійки

Спочатку визначте KnapsackPackage клас. The __lt__ метод дозволяє безпосередньо сортувати його за вартістю:

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

Потім реалізуйте процедуру дробового рюкзака:

class FractionalKnapsack(object):

    def knapsackGreProc(self, W, V, M, n):
        packs = [KnapsackPackage(W[i], V[i]) for i in range(n)]
        packs.sort(reverse=True)

        remain = M
        result = 0

        for i in range(n):
            if remain == 0:
                break
            if packs[i].weight <= remain:
                remain -= packs[i].weight
                result += packs[i].value
                print("Pack", i, "- Weight", packs[i].weight, "- Value", packs[i].value)
            else:
                fraction = remain / packs[i].weight
                result += packs[i].value * fraction
                print("Pack", i, "- Fraction", fraction,
                      "- Value", packs[i].value * fraction)
                remain = 0

        print("Max Value:", result)

Функція napsackGreProc() в Python

Виправлення примітки: оригінальні Python клас визначив порожній __init__ без тіла, що піднімає IndentationErrorУ версії вище порожній конструктор видаляється, оскільки він не потрібен.

Драйвер, який запускає алгоритм у першому прикладі:

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)

C# Code для Жадібної Трійки

Визначте 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   = value / weight;
        }

        public double Weight { get { return weight; } }
        public double Value  { get { return value; } }
        public double Cost   { get { return cost; } }
    }
}

Реалізуйте Greedy Three з кроком дробового заповнення:

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,
        (a, b) => b.Cost.CompareTo(a.Cost));

    double remain = M;
    double result = 0d;

    for (int i = 0; i < n && remain > 0; i++)
    {
        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);
        }
        else
        {
            double fraction = remain / packs[i].Weight;
            result += packs[i].Value * fraction;
            Console.WriteLine("Pack " + i + " - Fraction " + fraction
                            + " - Value " + packs[i].Value * fraction);
            remain = 0;
        }
    }

    Console.WriteLine("Max Value:\t" + result);
}

Функція KnapsackGreProc() у C#

Контрприклад: Жадібна трійця на рюкзаку 0/1

Жадібна трійка оптимальна для дробового варіанту, але на варіанті 0/1 Knapsack (де предмети не можна розділити) її можна перемогти. Контрприклад:

• Параметри: n = 3, M = 10.
• Пакети: {i = 1; W = 7; V = 9; вартість = 9/7}, {i = 2; W = 6; V = 6; вартість = 1}, {i = 3; W = 4; V = 4; вартість = 1}.
• Жадібна Трійка вибирає пакет 1 із загальною вартістю 9, тоді як оптимальний вибір 0/1 (пакет 2, пакет 3) досягає 10.

Урок: використовуйте метод «Жадібна три» лише тоді, коли дозволені дроби. Для варіанта 0/1 використовуйте Динамічне програмування замість цього.

Застосування дробового рюкзака

• Завантаження вантажів, де рідкі, порошкоподібні або сипучі товари можна розділити за вагою.
• Розподіл портфеля між інвестиційними варіантами, що приймають часткове фінансування.
• Спільне використання пропускної здатності в хмарі, де потоки можуть споживати лише частину з'єднання.
• Планування процесора за моделлю спільного часового інтервалу з розподіленими робочими навантаженнями.
• Розподіл ресурсів штучного інтелекту, де навчальне завдання може використовувати лише частину графічного процесора.

Поширені запитання