Задача о дробном рюкзаке: жадный алгоритм с примером

Что такое жадная стратегия?

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

Жадные алгоритмы обычно просты в написании, быстры (часто линейное или квадратичное время), легко отлаживаются и не требуют много памяти. Компромисс заключается в том, что результат не всегда оптимален, поэтому эта стратегия работает только для задач, имеющих доказанную структуру, безопасную для жадных алгоритмов.

Жадные стратегии решают задачу комбинаторной оптимизации, строя решение A по одному компоненту 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.

Идея «Жадной двойки»

Жадная Двойка сортирует посылки исключительно по весу:

• Расположите посылки в порядке убывания веса.
• Просмотрите отсортированный список и добавьте каждую посылку в рюкзак, если оставшаяся вместимость позволяет это сделать.

Это правило также не является оптимальным. Контрпример:

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

Идея «Жадной тройки»

Метод "Жадный три" исправляет обе ошибки, объединяя значение и вес в единый ключ ранжирования. Это стандартный метод для решения задачи о рюкзаке с дробными размерами.

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

Жадный Три сортирует по стоимости единицы V[i] / W[i]

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

Для истинного дробный В другом варианте, если следующая упаковка не помещается целиком, берётся доля, точно заполняющая оставшуюся вместимость. Именно это дополнительное правило делает стратегию «Жадные три» доказанно оптимальной в игре «Дробный рюкзак».

Этапы алгоритма

В варианте с ветвлением и ограничением 0/1 отсортированный список удельных затрат управляет деревом поиска:

• Шаг 1: Корневой узел представляет собой пустой рюкзак. TotalValue = 0. UpperBound = M × максимальная стоимость единицы.
• Шаг 2: Разветвление корневого узла осуществляется по количеству копий пакета с наибольшим соотношением размеров. Для каждого дочернего узла пересчитываются TotalValue, оставшаяся вместимость M и UpperBound.
• Шаг 3: Сначала расширьте матрицу для ребенка с наибольшей верхней границей, надеясь быстро найти надежное решение.
• Шаг 4: Удалите все узлы, у которых значение UpperBound не лучше, чем у текущего наилучшего полного решения.
• Шаг 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; }
}

Затем создайте функцию, реализующую алгоритм "Жадная тройка":

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);
}

Функция knapsackGreProc() в 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 класс. В __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)

Функция knapsackGreProc() в 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; } }
    }
}

Реализуйте алгоритм "Жадная тройка" с шагом дробного заполнения:

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.

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

Применение дробного рюкзака

• Погрузка грузов, при которой жидкие, порошкообразные или насыпные товары могут быть разделены по весу.
• Распределение средств в инвестиционном портфеле по вариантам инвестирования, допускающим частичное финансирование.
• Совместное использование полосы пропускания в облаке, при котором потоки могут потреблять лишь часть канала связи.
• Планирование работы ЦП в модели с разделяемым временным интервалом и делимыми рабочими нагрузками.
• Распределение ресурсов ИИ, при котором задача обучения может использовать лишь часть графического процессора.

Часто задаваемые вопросы (FAQ)