// Knapsack problem driver...
#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;

class Bundle {
public:
	unsigned int Weight;
	bool         Used;

	Bundle() {Weight = 0; Used = false;}
};

void loadData(Bundle List[], unsigned int Sz, const char* const fName);
bool Knapsack(Bundle List[], int Goal, unsigned int Start, unsigned int End);

int main(int argc, char** argv) {

	if ( argc < 2 ) {
		cout << "Invocation: Knapsack <data file>" << endl;
		return 1;
	}
	const unsigned int Sz = 10;
	Bundle List[Sz];

   loadData(List, Sz, argv[1]);
	if ( Knapsack(List, 100, 0, Sz - 1) ) {
		cout << "Solution found:" << endl;
		for (unsigned int Pos = 0; Pos < Sz; Pos++)
			if ( List[Pos].Used )
			   cout << setw(5) << List[Pos].Weight << endl;
	}
	else
		cout << "No solution found." << endl;

	return 0;
}

void loadData(Bundle List[], unsigned int Sz, const char* const fName) {

	ifstream In(fName);
	unsigned int Value;
	unsigned int Pos = 0;

	In >> Value;
	while ( In && Pos < Sz ) {
		List[Pos].Weight = Value;
		List[Pos].Used   = false;
		Pos++;
		In >> Value;
	}
	In.close();
}
	
bool Knapsack(Bundle List[], int Goal, unsigned int Start, unsigned int End) {

  if ( Goal == 0 )       // Success!  The empty collection
     return true;        //           adds up to 0.
  if ( Goal < 0 )        // We've overshot the goal
     return false; 	     
  if ( Start > End )     // We've run out of values
     return false; 	     

  // Try to extend current collection by including
  // List[Start]:
  cout << "Trying:     " << List[Start].Weight << endl;
  if ( Knapsack(List, Goal-List[Start].Weight, Start+1, End) ) {
     // Accept this value into the collection:
     List[Start].Used = true;
     return true;
  }
  else {  // No luck, so check for collection w/o List[Start]:
	  cout << "Rejected:   " << List[Start].Weight << endl;
	  return ( Knapsack(List, Goal, Start+1, End) );
  }
}