How do you create a knapsack using the bitwise & operator and the bitwise right-shift operator >> to decode the bit values of the different permutations in c++? Use cout.width( x ) and cout.setf( ios::left ) and cout.setf( ios::right ) to set an output field width, and to left and right and justify the output within that field for the tabular standard output.

This is the program that sets up the exhaustive-search knapsack problem. It reads lines from standard input in the following format. The first line contains a single integer giving the capacity of the knapsack. The remaining n lines each consist of two integers. The first integer is the items weight, and the second integer is the items value. A sample input file appears like this:

10 7 42 3 12 4 40 5 25 

How to make this program solve the knapsack problem using exhaustive search and using bit encoding to generate the subsets of items? A run of the program should look exactly like this:

$ ./knapsack < knapsackp118.dat { } 0 0 { 0 } 7 42 { 1 } 3 12 { 0 1 } 10 54 { 2 } 4 40 { 0 2 } 11 NF { 1 2 } 7 52 { 0 1 2 } 14 NF { 3 } 5 25 { 0 3 } 12 NF { 1 3 } 8 37 { 0 1 3 } 15 NF { 2 3 } 9 65 { 0 2 3 } 16 NF { 1 2 3 } 12 NF { 0 1 2 3 } 19 NF 123 456 

All the lines of output with curly braces must be on standard output. The very last line is on standard error. The first value (123 here, but is probably not the correct number) represents n, the input size, separated by a tab from the second value (456, again not correct) which is the count of basic operations.

Here is the c++ code that I have so far:

/** * a framework for exhaustive-search discrete knapsack */ #include  #include  #include  #include  #include  using namespace std; typedef unsigned int uint; /** * raise an unsigned integer to an unsigned power * C++ has pow, but it accepts and returns floating point values * @param base the base to be raised to a power * @param exp the exponent to which to raise the base * @return base ^ exp */ uint ipow(uint base, uint exp) { if( base == 0 ) return 1; uint result = 1; while( exp > 0 ) { if( (exp & 1) == 1 ) result *= base; exp >>= 1; base *= base; } return result; } /* * standard input must be of the form * capacity * weight value * weight value * ... */ int main() { uint capacity; cin >> capacity; vector weights; vector values; while( !cin.eof() ) { uint weight; uint value; cin >> weight >> value; if( !cin.eof() ) { weights.push_back( weight ); values.push_back( value ); } } }