How does knapsack work in exhaustive search and implement it?

Make a 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 run of your 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 

Though 123 and 456 may not be correct.

C++ code :

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