generate all subsets (2^n array)

[Robert Reid]

Hi there,

I'm wondering if anyone here can point me in the right direction. I'm
working on an exhaustive search for 0-1 knapsack problem.

I need to write some vba that will represent every possible combination of
items in the knapsack.

for example, if there are 3 items in the knapsack, I need to store the value
(v) of the items stored. Of course the knapsack capacity varies. In the
following example n= 3, i.e. there are 3 items to store, and 2^3 = 8
combinations of items.

000 = v1
010 = v2
001 = v3
011 = v4
111 = v5
101 = v6
110 = v7
111 = v8

I need to do this in vba as I'm unfamiliar with C, C++ or Java.

thanks in advance.

 

[Robert Reid]

Additionally, I've only been able to find solution in C language. One of
them uses bitfields (and bitwise operations) to generate array ( as
represented in previous thread). Can one create something similar to the
following C pseudo code in VBA ?

We just generate all bitfields. And what could be easier than to just use an
"int" variable, declare the lower N bits as our bitfield, and then count
from 0 to 2N-1 with that variable? Again, here's some outline:
for( int B=0; B<(1<<N); ++B ){
clearSubset();
for( int i=0; i<N; ++i )
if( (B & (1<<i)) > 0 )
addToSubset( element(i) );
useBuiltSubset();
}