Рюкзак - алгоритм грубой силы

Я нашел этот код для решения проблемы Knapsack с использованием механизма грубой силы (это в основном для обучения, поэтому нет необходимости указывать динамику более эффективно). Я получил код для работы и понимаю большую часть этого. БОЛЬШИНСТВО. Здесь вопрос:

Я заметил эти два условных выражения, что я понятия не имею, как они работают и почему они находятся в коде - я знаю, что они жизненно важны, поскольку любые изменения, которые я сделал, заставили алгоритм произвести неправильные результаты:

// if bit not included then skip
if (((i >> j) & 1) != 1) continue;

// if bit match then add
if (((bestPosition >> j) & 1) == 1)
{
    include.Add(Items[j]);
}

Здесь весь класс и способ, которым я вызываю его из main:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace KnapSack2
{
    class BruteForce
    {
        public double Capacity { get; set; }
        public Item[] Items { get; set; }

        public Data Run()
        {
            int bestValue = 0;
            int bestPosition = 0;
            int size = Items.Length;

            var permutations = (long)Math.Pow(2,size);

            for (int i = 0; i<permutations; i++)
            {
                int total = 0;
                int weight = 0;
                for (int j = 0; j<size; j++)
                {
                    //jeżeli bit "not included" to omin"
                    if(((i>>j)&1)!=1)
                        continue;
                    total += Items[j].v;
                    weight += Items[j].w;
                }
                if (weight <= Capacity && total>bestValue)
                {
                    bestPosition = i;
                    bestValue = total;
                }
            }
            var include = new List<Item>();
            for (int j = 0; j<size; j++)
            {
                // jeżeli bit pasuje, wtedy dodaj
                if (((bestPosition>>j) & 1)==1)
                    include.Add(Items[j]);
            }
            return new Data { BestValue = bestValue, Include = include };

        }//End of Run


    }
}

Вызов основного

var ks = new BruteForce
{
    Capacity = MaxWeight,
    Items = items.ToArray()
};

Data result = ks.Run();

Класс элемента - это просто значение объекта, вес и идентификатор

Ответы

Ответ 1

Этот & является bitwise-AND

Оператор bitwise-AND сравнивает каждый бит своего первого операнда с соответствующий бит его второго операнда. Если оба бита равны 1, соответствующий бит результата устанавливается равным 1. В противном случае соответствующий бит результата равен 0.

Пока этот >> является оператором с правым сдвигом

Оператор правого сдвига ( → ) сдвигает свой первый операнд справа на количество бит, заданных его вторым операндом.

Сказав это, возьмем следующее выражение

if (((i >> j) & 1) != 1) continue;

и попытайтесь понять это.

Изначально этот i >> j будет смещать правые биты i на позиции j.

Например, допустим следующее назначение:

int number = 5;

Двоичное представление number:

0000 0000 0000 0000 0000 0000 0000 0101

Если мы определяем новое целое число как:

int shiftNumbersBitByOne = a >> 1;

Тогда двоичное представление shiftNumbersBitByOne будет:

0000 0000 0000 0000 0000 0000 0000 0010

Затем по результату этой операции и 1 мы применяем побитовый оператор И.

Что именно этот оператор?

Несмотря на то, что определение ясно, пример сделает его более понятным.

Пусть у нас есть двоичные числа a и b, то результатом a&b является следующее:

a =     0001 0100 1010 0001 1000 1010 1101 0011
b =     0010 1100 1111 0111 0011 1010 1011 0111
a & b = 0000 0100 1010 0001 0000 1010 1001 0011

При этом в этой операции (i >> j) & 1 мы применяем побитовый-И-оператор между результатом i >> j и двоичным представлением 1

0000 0000 0000 0000 0000 0000 0000 0001

Когда результатом (i >> j) & 1 будет 1?

Это произойдет тогда и только тогда, когда последняя цифра i >> j равна 1.

Обновление

Выше мы обратились к части как - я понятия не имею, как они работают. Теперь мы рассмотрим часть почему - почему они находятся в коде.

Давайте определим нашу проблему, проблему Рюкпак. Согласно wikipedia

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

В соответствии с вышесказанным, просто, что

// This is the total weight limit.
public double Capacity { get; set; }

и

// This is an array with all the given items.
public Item[] Items { get; set; }

Кроме того, на основе вашего кода мы можем сделать вывод, что каждый элемент имеет значение и вес, к которым можно получить доступ как item.v и item.w соответственно. Я предлагаю вам переименовать его в значение и вес соответственно, чтобы ваш код был более значимым.

По-видимому, это int size = Items.Length; - количество доступных элементов.

Весь смысл того, почему часть начинается здесь:

var permutations = (long)Math.Pow(2,size);

Что такое permutations? Что означает permutations?

Прежде чем ответить на этот вопрос, подумайте о том, как мы можем представить, какие элементы коллекции предметов будут использоваться в конечном решении. Я утверждаю, что мы можем представить это с n-битным числом при условии, что у нас есть n элементов. Как это возможно? Если каждый бит в n-битовом номере относится к одному из n-элементов, довольно очевидно, что мы можем это сделать. Значение n-го бита будет 0, если n-й элемент не будет включен в окончательное решение. Хотя это значение будет равно 1, если оно будет включено.

Говоря довольно ясно, что представляют собой перестановки. Он представляет все возможные комбинации элементов в конечном решении. Это понятно, потому что каждый бит может иметь 2 значения, либо 0, либо 1. Учитывая, что у нас есть n-биты, число возможных комбинаций равно 2 ^ n.

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

for (int i = 0; i<permutations; i++)
{ 
    // ...
}

вы выполняете все возможные комбинации.

Затем для каждой комбинации вы просматриваете коллекцию предметов:

for (int j = 0; j < size; j++)
{
    // Here you check if the item in position j
    // is included in the current combination.
    // If it is not, you go to the next value of the loop variable
    // and you make the same check.
    if(((i>>j)&1)!=1)
        continue;

    // The j-th item is included in the current combination. 
    // Hence we add it's
    // value to the total value accumulator and it weight to 
    // the total weight accumulator.
    total += Items[j].v;
    weight += Items[j].w;
}

Теперь, если значение weight меньше предельного значения и, общее значение больше, чем лучшее текущее общее значение, мы выбираем эту комбинацию как лучшую в настоящий момент:

bestPosition = i;
bestValue = total;

В конце концов, пройдя все доступные комбинации, у нас будет лучший.

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

// The include is a list that will hold the items of the best combination.
var include = new List<Item>();

// We loop through all the available items
for (int j = 0; j<size; j++)
{
    // If the items is included in the best combination,
    // add this item to the include list.
    if (((bestPosition>>j) & 1)==1)
        include.Add(Items[j]);
}

Ответ 2

По-видимому, рассматриваемые части кода проверяют наличие определенного бита, о чем свидетельствуют комментарии. Условие

((i >> j) & 1) != 1

истинно тогда и только тогда, когда j -th бит i равен нулю; условие

((bestPosition >> j) & 1) == 1

истинно тогда и только тогда, когда j -th бит bestPosition является одним. Что касается большей картины, то, по-видимому, в реализации используется int для моделирования набора элементов, где j -th бит устанавливается тогда и только тогда, когда j -th элемент включен в набор; следовательно, тесты на членство могут выполняться с помощью проверки бит. Реализация перечисляет все подмножества элементов (используя int для их представления) для выполнения исчерпывающего поиска.

Обратите внимание, что реализация Delphi для наборов использует тот же подход, но скрывает индексацию битов от кода клиента.