Задача о ранце

Задача о ранце (рюкзаке) — одна из задач комбинаторной оптимизации. Название это получила от максимизационной задачи укладки как можно большего числа нужных вещей в рюкзак при условии, что общий объём (или вес) всех предметов, способных поместиться в рюкзак, ограничен. Подобные задачи часто возникают в экономике, прикладной математике, криптографии. В общем виде, задачу можно сформулировать так: из неограниченного множества предметов со свойствами «стоимость» и «вес», требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при одновременном соблюдении ограничения на суммарный вес.

Разновидности

1. Каждый предмет из множества можно выбирать произвольное количество раз.
2. Каждый предмет можно использовать только один раз.

Решение

Задача о ранце в случае, когда вес каждого предмета представляет собой целое число, может быть решена с помощью динамического программирования. Но важно отметить, что задача о ранце является NP-задачей (псевдо-полиномиальна).

Задача о ранце с возможностью бесконечного выбора предметов

Формулировка

По данному набору из n предметов стоимостями v₁,v₂,...,v_n и весами w₁,w₂,...,w_n найти поднабор (с учетом того, что можно брать один предмет несколько раз) такой, что его стоимость будет максимальна среди всех поднаборов веса не более W.

Решение

Обозначим через K_w максимальную стоимость, которую мы можем набрать при весе не более w. Получаем следующее рекуррентное соотношение:

• K₀ = 0 (при весе не более нуля максимальная стоимость 0)
• $K_w = max \{ K_{w-w_i} + v_i | w_i \leq w,\ 1 \leq i \leq n \}$, где n - размер набора

Использовать рекурсию напрямую нельзя, т.к. появляется большое число перекрывающихся задач и время выполнения может стать экспоненциальным. При использовании динамического программирования(запоминания) мы получаем сложность O(n * W) - псевдополиномиальный алгоритм.

Реализация

C++

#include <vector>
#include <limits>
 
//wts - массив весов, cost - массив стоимостей предметов, W - вместимость рюкзака
//функция возвращает максимальную стоимость, которую можно набрать(решение задачи о рюкзаке
//с повторениями)
//массив dp собственно реализует динамическое программирование, описанное в статье, как K_w
int knapsack1(const std::vector<int>& wts, const std::vector<int>& cost, int W)
{
        size_t n = wts.size();
        std::vector<int> dp(W + 1);
        dp[0] = 0;
        for (int w = 1; w <= W; w++)
        {
                dp[w] = dp[w-1];
                for (size_t i = 0; i < n; i++)
                {
                        if (wts[i] <= w)
                        {
                                dp[w] = std::max(dp[w], dp[w - wts[i]] + cost[i]);
                        }
                }
        }
        return dp[W];
}

Задача о ранце с возможностью единичного выбора предмета

Решение

Обозначим через K_w,i максимальную стоимость, которую мы можем набрать при весе не более w среди i первых предметов. Получаем следующее рекуррентное соотношение:

• $K_{0, j} = 0, \quad 0 \le j \le n$
• $K_{w, 0} = 0, \quad 0 \le w \le W$
• $K_{w, i} = \begin{cases} \max{ \left( K_{w, i - 1}, K_{w-w_i, i - 1} + v_{i} \right) }, \quad w_i \le w \\ K_{w, i - 1}, \quad w_i > w \end{cases}, 0 \le w \le W$

Реализация

C++

#include <vector>
#include <limits>
 
int knapsack2(const std::vector<int>& wts, const std::vector<int>& cost, int W)
{
    size_t n = wts.size();
    std::vector<std::vector<int> > dp(W + 1, std::vector<int>(n+1, 0));
    for (size_t j = 1; j <= n; j++)
    {
        for (int w = 1; w <= W; w++)
        {
            if (wts[j-1] <= w)
            {
                dp[w][j] = std::max(dp[w][j - 1], dp[w - wts[j-1]][j - 1] + cost[j-1]);
            }
            else
            {
                dp[w][j] = dp[w][j - 1];
            }
        }
    }
    return dp[W][n];
}

Java

int knapsack(int weights[], int costs[], int needed) {
    int n = weights.length;
    int dp[][] = new int[needed + 1][n + 1];
    for (int j = 1; j <= n; j++) {
        for (int w = 1; w <= needed; w++) {
            if (weights[j-1] <= w) {
                dp[w][j] = Math.max(dp[w][j - 1], dp[w - weights[j-1]][j - 1] + costs[j-1]);
            } else {
                dp[w][j] = dp[w][j - 1];
            }
        }
    }
    return dp[needed][n];
}

C#

int knapsack(int[] weights, int[] costs, int needed)
{
    int n = weights.Length;
    int[,] dp = new int[needed + 1, n + 1];
    for (int j = 1; j <= n; j++)
    {
        for (int w = 1; w <= needed; w++)
        {
            if (weights[j - 1] <= w)
            {
                dp[w, j] = Math.Max(dp[w, j - 1], dp[w - weights[j - 1], j - 1] + costs[j - 1]);
            }
            else
            {
                dp[w, j] = dp[w, j - 1];
            }
        }
     }
     return dp[needed, n];
}

Free Pascal

procedure rec(k,w,st:longint);
var i:longint;
begin
  for i:=1 to n do
    if b[i] and(w>=weight[i]) then
      begin
        b[i]:=false;
        now[k]:=i;
        rec(k+1,w-weight[i],st+price[i]);
        b[i]:=true;
      end
    else
      begin
        if (st>maxprice) then
          begin
            best:=now;
            maxprice:=st;
          end;
      end;
end;

См. также

• Задача об упаковке в контейнеры
• Метод ветвей и границ
• Дискретное программирование
• Математическое программирование
• Оптимизация
• Исследование операций

Ссылки

Пример решения целочисленной задачи о ранце методом Гилмора-Гомори

Пример решения бивалентной задачи о ранце методом Гилмора-Гомори

Литература

• Ананий В. Левитин Глава 3. Метод грубой силы: Задача о рюкзаке // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms — М.: «Вильямс», 2006. — С. 160-163. — ISBN 0-201-74395-7.
• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = Introduction to Algorithms — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1.
• Роберт Седжвик. Фундаментальные алгоритмы на C++. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск = Algorithms in C++. Parts 1-4. Fundamentals. Data Structures. Sorting. Searching — 3-е изд. — Россия, Санкт-Петербург: «ДиаСофт», 2002. — С. 688. — ISBN 5-93772-047-4, 0-201-35088-2.