Create and fill a variable-sized binary truth table

Question

I am trying solve the 0/1 Knapsack problem through brute force. The simplest (it seems) way to do it would be to set up a 2d matrix with 1's and 0's signifying present and non-present in the knapsack, respectively. The parameters would be the number of items (ie: columns), so then the rows should be 2^numOfItems. But since the number of items isn't constant, I can't think of how to fill the matrix. I was told that bit-shifting would work, but I do not understand how that works. Can someone point me in the right direction?

EDIT: by truth table I mean the 'A' part of one of these: http://www.johnloomis.org/ece314/notes/devices/binary_to_BCD/bcd03.png

Answer 1

You don't have to store all the bit sequences in a matrix, it's unnecessary and will waste way too much memory. You can simply use an integer to denote the current set. The integer will go from 0 to 2^n-1 where n is the number of elements that you can choose from. Here's the basic idea.

int max = (1 << n);
for(int set = 0; set < max; set++)
{
    for(int e = 0; e < n; e++)
    {
        if((set & (1 << e)) != 0)
           //eth bit is 1 means that the eth item is in our set
        else
           // eth element will not be put in the knapsack
    }
}

The algorithm relies on logical left bit shifting. (1 << n) means that we will shift 1, n positions to the left by padding zeros to the right side of the number. So for example, if we represent 1 as an 8-bit number 00000001, (1 << 1) == 00000010, (1 << 2) == 00000100, etc. The bitwise-and operator is an operator that takes two arguments, and "ands" every two bits that have the same index. So if we have 2 bit-strings of length n each, bit zero will be anded with bit 0, bit 1 with bit 1, etc. The output of & is a 1 if and only if both bits are 1s, otherwise it's 0. Why is this useful?? we need it to test bits. For example, assume that we have some set represented as a bit-string, and we want to determine if the ith bit in the bit-set is one or a zero. We can do that by using a shift left operation followed by a bitwise-and operation.

Example

Set = 00101000 we want to test Set(3) (remember that the rightmost bit is bit 0) We can do that by shifting 1 3 places to the left, so it becomes 00001000. Then we "and" the shifted 1 with the set

00101000
         &
00001000
---------
00001000

As you can see, if the bit I am testing is a 1, then the output of the & will be non zero, otherwise it'll be zero.