Рюкзак и его разновидности

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

• 0-1 knapsaсk - каждый предмет мы можем брать не более одного раза
• unbounded knapsack - можно взять неограниченное количество каждого предмета
• bounded knapsack - максимальное количество каждого предмета ограниченно сверху

Данную задачу можно решить с помощью динамического программирования. Для решения всех трех поздачач используются двухмерная таблица. Элемента таблицы в i-ой строке и j-ом столбце это максимальная сумма которую можно набрать используя первые i предметов так чтобы суммарные вес предметов в наборе был равен j.

0-1 Knapsack

Для решения нам необязательно хранить всю таблицу. Достаточно хранить текущую строку и обновлять ее для каждого нового предмета. При добавлении нового предмета для каждого веса от 0 до W мы можем либо использовать этот предмет, либо обойтись только предыдущими в зависимости от полученной стоимости. Веса нужно просматривать в порядке убывания чтобы при просмотре сохраненного значения с меньшим весом мы использовали значение без учета нового предмета.

vector<int> O1_knapsack(vector<Item> &A, int W)
{
    int n = sz(A);
    vector<int> dp = vector<int>(W + 1, -INF);
    dp[0] = 0;
    for (int k = 1; k <= n; ++k) {
        int wk = A[k - 1].w; // вес
        int ck = A[k - 1].c; // стоимость
        for (int w = W; w >= wk; --w) {
            if (dp[w - wk] != -INF) {
                dp[w] = max(dp[w], dp[w - wk] + ck);
            }
        }
    }
    return dp;
}

Unbounded knapsack

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

vector<int> unbounded_knapsack(vector<Item> &A, int W)
{
    int n = sz(A);
    vector<int> dp = vector<int>(W + 1, -INF);
    dp[0] = 0;
    for (int k = 1; k <= n; ++k) {
        int wk = A[k - 1].w; // вес
        int ck = A[k - 1].c; // стоимость
        for (int w = wk; w <= W; ++w) {
            if (dp[w - wk] != -INF) {
                dp[w] = max(dp[w], dp[w - wk] + ck);
            }
        }
    }
    return dp;
}

Bounded knapsack

Данную задачу можно свести к 0-1 knapsack добавив необходимое количество копий каждого предмета. Однако это существенно увеличивает сложность при больших значениях ограничений на количество предмета - O(NWU), где U - максимум среди ограничений. Можно улучшить эту оценку до O(NWlogU) добавив для каждого предмета веса по степеням двойки. Это даст возможность набрать любой вес от 0 до Wk*Uk. При этом количество весов будет log(Uk). Например если у нас есть Wk=1 и Uk=20 то мы получим веса 1,2,4,8,5 и это даст нам возможность представить любой вес от 1 до 20.

Однако, существует способ решить эту задачу как и предыдущие рассмотренные за время O(NW). Заметим, что

dp[k][w] это минимум среди:

dp[k - 1][w - 0 * wk] + 0 * ck

dp[k - 1][w - 1 * wk] + 1 * ck 

dp[k - 1][w - 2 * wk] + 2 * ck

....

dp[k - 1][w - uk * wk] + uk * ck

Мы можем разбить все веса от 0 до W на группы по остатку от деления веса на wk и в пределах каждой группы мы должны быстро считать максимум в окне из (uk + 1) элементов из массива dp[k - 1] с некоторым добавочным значением. 

Иными словами имеем следующую задачу. У нас есть массив A из N элементов, необходимо рассчитать максимум для каждого окна размера K, где элемент окна на позиции i равен A[shift+i] + X*i, где shift - смещение окна, X - некоторая константа. Задача поиска минимума в окне массива решается стандартно с использованием алгоритма поиска максимума в очереди. В данном случае необходима неболшая модификация. Добавим к i-ому элементу массива A величину i*X. Тогда, когда мы будем получать очередной максимум для окна со сдвигом shift мы будем получать максимум для элементов:

A[shift] + shift*X,

A[shift+1] + (shift+1)*X,

...

A[shift+K-1] + (shift+K-1)*X.

Т.е. чтобы получать интересующий нас максимум мы должны из полученного значения вычесть shift*X. Адаптировав это для решения поставленной задачи можно получить следующий код:

Queue q;
vector<int> bounded_knapsack(vector<Item> &A, int W)
{
    int n = sz(A);
    vector<vector<int>> dp = vector<vector<int>>(2, vector<int>(W + 1, INF));
    dp[0][0] = 0;
    int prev = 0, cur = 1;
    for (int k = 1; k <= n; ++k) {
        int wk = A[k - 1].w;  // вес
        int ck = A[k - 1].c;  // стоимость
        int uk = A[k - 1].u;  // максимальное количество
        for (int sw = 0; sw < wk && sw <= W; ++sw) {
            q.clear();
            int cum = 0;
            for (int w = sw; w <= W; w += wk, cum += ck) {
                if (dp[prev][w] == INF) {
                    q.push(INF);
                } else {
                    q.push(dp[prev][w] - cum);
                }
                while (q.size() > uk + 1) q.pop();
                dp[cur][w] = q.get();
                if (dp[cur][w] != INF) {
                    dp[cur][w] += cum;
                }
            }
        }
        swap(prev, cur);
    }
    return dp[prev];
}

Задачи:

Счастливая страна

Определение минимального элемента в очереди за константное время

Структура данных очередь используется во многих алгоритмах. Помимо стандартных операций иногда существует необходимость в получении минимального (максимального) элемента за константное время. Поддержка такой статистики со стеком реализуется тривиально - вместе с добавленным элементом сохраняется минимум всех элементов на стеке (рассчитывается как минимум из добавленного элемента и значения минимума предыдущих значений на стеке). Этот подход адаптируется и для очереди. Как известно очередь можно реализовать с помощью двух стеков: стек для добавления элементов S1 и стек для изъятия элементов S2. Т.е. любое добавление в очередь добавляет элемент в S1, а любое изъятие проверяет стек S2 и если он пустой, то  перекладывает все элементы из S1 в S2. После этого извлекает элемент с вершины стека S2. Т.о. реализовав очередь с помощью двух стеков с поддержкой минимального элемента, мы в любой момент можем получить минимум в очереди как минимум минимальных элементов стека S1 и S2.

#define ZERO (1LL<<60)
#define ADD(x, y) (min((x), (y)))

typedef pair<lint, lint> plii;
typedef long long lint;

const int MAX = 1000000 + 10;

struct Queue {
    
    plii v1[MAX], v2[MAX];
    int n1, n2;
    
    Queue() {
        clear();
    }
    
    void push(lint x) {
        v1[n1] = mp(x, ADD(x, v1[n1 - 1].second));
        n1++;
    }
    
    void pop() {
        if (n2 == 1) {
            while (n1 > 1) {
                lint x = v1[--n1].first;
                v2[n2] = mp(x, ADD(x, v2[n2 - 1].second));
                n2++;
            }
        }
        n2--;
    }
    
    lint get() {
        return ADD(v1[n1 - 1].second, v2[n2 - 1].second);
    }
    
    int size() {
        return n1 + n2 - 2;
    }
    
    void clear() {
        n1 = n2 = 0;
        v1[n1++] = mp(ZERO, ZERO);
        v2[n2++] = mp(ZERO, ZERO);
    }
};

Данная структура данных применяется в следующих задачах:
- рюкзак с ограничением количества элементов. Позволяет решить задачу за O(NW)
- поиск минимума во всевозможных диапозонах массива фиксированной длины (скользящее окно по массиву)

Topcoder - подключение плагина moj

Для того чтобы упростить себе жизнь в соревнованиях топкодер существует различные плагины.
Рассматриваемые в этом посте плагин moj умеет следующее:

• генерировать скелет решения (класс и метод) и сохранять его в указанное место
• включить в сгенерированный скелет необходимый prewritten код
• генерировать по сэмплам из условия задачи код, необходимый для тестирования

1. Для начала качаем архив с необходимыми файлами по ссылке
2. После этого заходим в арену, выбираем Options->Editor->Add. В появившемся диалоге указываем:

• Name: CodeProcessor
• EntryPoint: codeprocessor.EntryPoint
• ClassPath: нажимаем browse и выбираем все jar файлы из скаченного архива (moj.jar, CodeProcessor.jar, FileEdit.jar)

3. Нажимаем Configure и в поле Editor Entry Point пишем fileedit.EntryPoint и ниже добавляем строчку с содержимым moj.moj.
4. Снова нажимаем Configure для того чтобы задать настройки плагина. Здесь необходимо указать имя директории куда будут сохраняться сгенерированные файлы. Кроме того рекомендуется снять галочку Backup existing file then overwrite. Наконец, нужно вставить код шаблона для используемого языка программирования. Так, для C++ он может выглядеть следующим образом:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

#include <iostream> #include <sstream> #include <cmath> #include <string> #include <string.h> #include <cstdio> #include <vector> #include <queue> #include <map> #include <set> #include <algorithm> #include <cassert> using namespace std; #define all(x) (x).begin(), (x).end() #define pb push_back #define mp make_pair #define sz(x) ((int)((x).size())) #define rep(i, N) for (int i = 0; i < N; ++i) #define foreach(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();++it) typedef long long lint; typedef vector<string> vs; typedef vector<int> vi; typedef pair<int, int> pii; class $CLASSNAME$ { public: $RC$ $METHODNAME$( $METHODPARMS$ ) { } }; $BEGINCUT$ $TESTCODE$ $DEFAULTMAIN$ $ENDCUT$