[Из песочницы] Задача о ранце и код Грея

Не так давно на Хабре была статья «Коды Грея и задачи перебора». Статья эта скорее, математическая, нежели программистская, и мне, как простому программисту, читать её было невыносимо тяжело. Но сама тема мне знакома, поэтому я решил описать её своим взглядом, а так же рассказать о том, как использовал её в решении задачи о ранце.

КДПВ: задача о ранце на живом примере

Предыстория

Всё началось 10 лет назад, когда я учился в девятом классе. Я случайно подслушал разговор учителя по информатике, рассказывающего задачку кому-то из старших: дан набор чисел, и ещё одно число — контрольное. Надо найти максимальную сумму чисел из набора, которая не превышала бы контрольное число.

Задача почему-то запала мне в душу. Вернувшись домой, я быстро накатал решение: наивный перебор всех возможных сумм с выбором наилучшего. Сочетания я получал, перебирая все N-разрядные двоичные числа и беря суммы тех исходных чисел, которым соответствуют единицы. Но я с огорчением обнаружил, что при количестве элементов начиная где-то с 30, программа работает очень долго. Оно и не удивительно, ведь время работы такого алгоритма — n*2ⁿ (количество сочетаний, умноженное на длину суммы).



Прошло 5 лет. Я успел закончить школу и поступить в университет, но эта задача по-прежнему была со мной. Один раз, листая книгу «Алгоритмические трюки для программистов» (Hacker's Delight / Henry S. Warren Jr.), я наткнулся на описание кода Грея: это последовательность двоичных чисел, каждое из которых отличается от предыдущего только одним битом. «Стоп!» — подумал я — «Это означает… Да! Это означает, что в той самой задаче на каждом шаге перебора можно не считать сумму целиком, а лишь добавлять или вычитать одно число». И я тут же углубился в изучение темы.

Построение кода Грея

Код Грея можно построить для числа любой разрядности. Для одного разряда он очевиден:

0

1

Чтобы добавить второй разряд, можно к этой последовательности дописать такую же задом наперёд

0

1

1

0

и ко второй половине дописать единицы:

00

01

11

10

Аналогично для трёх разрядов:

000

001

011

010

110

111

101

100

Такой код, полученный отражением кода меньшей разрядности, называется рефлексным (отражённым) кодом Грея. Бывают и другие последовательности, но на практике обычно используется именно эта.

Этот код назван в честь Фрэнка Грея, который изобрёл ламповый АЦП, выдававший цифровой сигнал именно в этом коде. При небольших изменениях уровня входного сигнала цифровой выход мог измениться только в одном бите, и этим исключались резкие скачки из-за неодновременного переключения битов.

Иллюстрация патента Фрэнка Грея

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

Датчик абсолютного угла поворота. Оптические щели расположены в соответствии с кодом Грея

Применение в задаче о ранце

Но вернёмся к задаче о ранце. Стандартная формула даёт нам код Грея по номеру:

G = i ^ (i >> 1)

По ней мы можем только посчитать сумму все нужных элементов. А мы собирались на каждой итерации добавлять или вычитать одно значение, верно? Значит, нам нужно получить номера изменяемых битов. Для многоразрядных чисел эти номера будут такими:

0

1

0

2

0

1

0

3

0

1

0

2

0

1

0

4

…

Ничего не напоминает? Это номер бита, который мы устанавливаем в единицу, когда просто перечисляем обычные двоичные числа. Или иначе — номер младшей единицы в двоичном числе. Эта операция называется find first set и в большинстве процессоров существует в виде отдельной инструкции. Visual C++ предоставляет эту инструкцию в виде функции _BitScanForward.

Итак, теперь мы готовы написать программу, решающую задачу о ранце через код Грея. Сформулируем задачу так:

В файле input.txt в первой строке указана вместимость рюкзака, а в остальных строках — размеры вещей. В консоль нужно вывести максимальную загрузку рюкзака и размеры выбранных вещей. Проверку корректности ввода и пр. — нафиг.

Мы будем хранить битовую маску использованных вещей, и по мере необходимости добавлять или убирать одну из них. Чтобы обойтись int-ами, ограничим количество вещей (и используемых бит) тридцатью одной.

#include <iostream>
#include <fstream>
#include <bitset>
#include <intrin.h>
using namespace std;

void main()
{
    int target;        // размер ранца
    int nItems = 0;    // количество предметов
    int weight[31];    // веса предметов
    ifstream inFile("input.txt");
    inFile >> target;
    while(inFile >> weight[nItems])
        nItems++;
    inFile.close();

    const unsigned int nIterations = 1 << nItems; // количество комбинаций, 2^n
    int sum = 0;                   // текущий вес вещей
    int bestSum = 0;               // лучший вес (максимальный без перегрузки)
    bitset<31> mask;               // текущая комбинация выбранных вещей
    bitset<31> bestMask;           // лучшая комбинация выбранных вещей
    for (unsigned int i = 1; i < nIterations; i++)
    {
        unsigned long position;    // какой по счёту бит инвертируем
        _BitScanForward(&position, i);
        mask[position] = !mask[position];
        if (mask[position])        // кладём в рюкзак или убираем эту вещь
            sum += weight[position];
        else
            sum -= weight[position];

        if (sum > target)          // перегруз
            continue;
        if (sum > bestSum)         // Отличный вариант! Надо запомнить...
        {
            bestSum = sum;
            bestMask = mask;
        }
    }

    cout << "Best approximation: " << bestSum << endl;
    cout << "Used weights:" << endl;
    for (int i = 0; i < 31; i++)
        if (bestMask[i])
            cout << weight[i] << endl;
    cin.get();
}

Прощу прощения за возможные шероховатости; к сожалению, C++ уже давно не мой профильный язык.

Работает действительно быстрее, чем сборка с нуля всех сумм, разница заметна уже при 20 числах, а при 30-и я так и не дождался выполнения наивного алгоритма, в то время как новый вариант выполняется за 7 секунд. Впрочем, учитывая экспоненциальную сложность, это совсем не мало: для 50 чисел использовать этот алгоритм уже нет смысла. К сожалению, любой точный алгоритм будет работать не быстрее, чем за 2ⁿ; быстрее возможно только приблизительное решение.

Наверное, именно поэтому я обречён до конца жизни нести свой ранец, пытаясь ускорить эту программу. Я уже однажды переписывал цикл на ассемблере, получив небольшой прирост в скорости, а сейчас даже подумываю сделать многопоточную версию программы. Вам же остаётся лишь мне посочувствовать. :)

This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at fivefilters.org/content-only/faq.php#publishers.