Частичен проблем с раницата: алчен алгоритъм с пример

Какво е Greedy Strategy?

Алчни алгоритми избират най-добрия локален избор на всяка стъпка с надеждата, че верига от локални оптимуми ще доведе до глобално оптимално решение. Подобно на динамичното програмиране, те са насочени към оптимизационни проблеми, но никога не се обръщат назад, за да преосмислят по-ранни решения.

Алчните алгоритми обикновено са лесни за писане, бързи (често линейно или квадратично време), лесни за отстраняване на грешки и изискват малко памет. Компромисът е, че резултатът не винаги е оптимален, така че стратегията работи само за проблеми, които имат доказано безопасна за алчност структура.

Алчните стратегии решават комбинаторната оптимизация чрез изграждане на решение А с по един компонент Ai в даден момент. На всяка стъпка избирате Ai оптимално при текущите ограничения и свивате проблема до по-малък подзадач.

За да бъде коректен един алчен метод, трябва да са налице две свойства:

1. Свойство на алчен избор: Локалният оптимум на всяка стъпка води до глобален оптимум. Изборът зависи от минали решения, но не и от бъдещи.
2. Оптимална подструктура: Оптималното решение на целия проблем съдържа оптимални решения на неговите подзадачи.

Един алчен алгоритъм има пет компонента:

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

Идеята на 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() in 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() in 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 (където предметите не могат да се разделят) може да бъде победена. Контрапример:

• Параметри: 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.

Урокът: използвайте Greedy Three само когато са разрешени дроби. За варианта 0/1 използвайте Динамично програмиране вместо.

Приложения на дробната раница

• Товарене на товари, при което течни, прахообразни или насипни товари могат да бъдат разделени по тегло.
• Разпределение на портфолиото между инвестиционни опции, които приемат частично финансиране.
• Споделяне на честотна лента в облака, където потоците могат да консумират част от връзката.
• Планиране на процесора по модел със споделен времеви интервал с делими натоварвания.
• Разпределение на AI ресурси, при което обучителна задача може да използва част от GPU.

Въпроси и Отговори