Knapsack - brute force algorithm

Question

I have found this code to solve Knapsack Problem using brute force mechanism (this is mostly for learning, so no need to point out dynamic is more efficient). I got the code to work, and understand most of it. MOST. Here's the question:

I've noticed those two conditionals, that I have no idea how they work and why they are in the code - I know they are vital, since any changes I've made caused the algorithm to produce wrong results:

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

Here's the whole class, and the way I'm calling it out from 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


    }
}

Calling out in main

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

Data result = ks.Run();

Item class is just a simple object holding value, weight and ID

Answer 1

This & is the bitwise-AND

The bitwise-AND operator compares each bit of its first operand to the corresponding bit of its second operand. If both bits are 1, the corresponding result bit is set to 1. Otherwise, the corresponding result bit is set to 0.

While this >> is the right-shift operator

The right-shift operator (>>) shifts its first operand right by the number of bits specified by its second operand.

That being said, let's take the following expression

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

and try to understand it.

Initially, this i >> j will shift right the bits of i by j positions.

For instance, let we have the following assignment:

int number = 5;

The binary representation of number is:

0000 0000 0000 0000 0000 0000 0000 0101

If we define a new integer as:

int shiftNumbersBitByOne = a >> 1;

Then binary representation of shiftNumbersBitByOne would be:

0000 0000 0000 0000 0000 0000 0000 0010

Then on the result of this operation and 1, we apply the bitwise AND operator.

What does exactly this operator ?

Despite the fact that the definition is clear, an example will make it more clear.

Let that we have the binary numbers a and b, then the result of a&b is the following:

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

That being said, in this operation (i >> j) & 1 we apply the bitwise-AND operator between the result of i >> j and the binary representation of 1

0000 0000 0000 0000 0000 0000 0000 0001

When the result of (i >> j) & 1 would be 1?

This will happen if and only if the last digit of i >> j is 1.

Update

Above we addressed the how part -I have no idea how they work. Now we will address the why part -why they are in the code.

Let's define our problem, the Knapsack problem. According to wikipedia

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a mass and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

According to the above, it is straightforward that

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

and

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

Furthermore, based on your code, we can deduce that each item has a value and a weight that can be accessed as item.v and item.w respectively. I suggest you rename this to value and weight respectively, in order your code to be more meaningful.

Apparently, this int size = Items.Length; is the number of the available items.

The whole point of why part starts here:

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

What is the permutations? What does permutations represent?

Before we answer this question, let's think about how we can represent which items of the items collection will be used in the final solution. I argue that we can represent this with a n-bit number provided that we have n items. How is that possible? If each bit in the n-bit number refers to one of the n-items, it is pretty evident we can do so. The value of the n-th bit would be 0, if the n-th item will not be included in the final solution. While it's value would be 1, if it will be included.

That being said is pretty clear what permutations represents. It represents all the possible combinations of the items in the final solution. This is clear, because each bit can have 2 values, either 0 or 1. Given that we have n-bits, the number of the possible combinations is 2^n.

Actually, for this reason this algorithm is a brute force algorithm (we do an exhaustive search). We visit all the possible combinations to find the best one. In the following loop:

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

you loop through all the possible combinations.

Then foreach combination, you loop through the items collection:

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's 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's weight to 
    // the total weight accumulator.
    total += Items[j].v;
    weight += Items[j].w;
}

Now if the weight is less than the limit value and the total value is greater than the best current total value, we pick this combination as the current best:

bestPosition = i;
bestValue = total;

At the end, having looped through all the available combinations, we will have the best one.

Having found the best combination, we have to loop through the items to see which of them are included in this combination.

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

Answer 2

Apparently the code parts in question are checks for a certain bit being set, as indicated by the comments. The condition

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

is true if and only if the j-th bit of i is zero; the condition

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

is true if and only if the j-th bit of bestPosition is one. Concerning the bigger picture, apparently the implementation uses int to model a set of items, where the j-th bit is set if and only if the j-th item is included in the set; consequently, membership tests can be done by bit checks. The implementation enumerates all subsets of the items (using int to represent them) to perform exhaustive search.

Note that the Delphi implementation for sets uses the same approach, but hides the bit indexing from client code.