How do you create a knapsack using the bitwise & operator and the bitwise right-

Question

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 item’s weight, and the second integer is the item’s value. A sample input file appears like this:

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:

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:

Explanation / Answer

Arithmetic shift right operator

x >> y

Returns x with the bits shifted to the right by y places. This is same as dividing x by 2**y for an unsigned integer. Right shift of a negative signed number has implementation-defined behaviour. Most of the compilers throw a warning when you shift with a count >= sizeof(type). Shifting it right may fill "empty" bits with the original Most Significant Bit (i.e. perform sign extension) or it may shift in zeroes, depending on platform and/or compiler.

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.