/*************************************************************
 *							     *
 *      Program Solving the KNAPSACK problem 		     *
 *	 using Branch&Bound (B&B) algorithm		     *
 *      Author Jakub Holy                                    *
 *      For the subject PAA, LS2002                          *
 *      branch_bound.cc is based on hw1_force.cc             *
 *							     *
 *************************************************************
 */
// 	$Id: branch_bound.cc.html,v 1.1.1.1 2003/11/08 13:19:49 aja Exp $	

using namespace std;
#include <iomanip>

#include "branch_bound.hh"
// #ifndef NDEBUG
// #define NDEBUG	// remove assert(...)

// *** ******************************************** Branch_BoundAlgorithm
Branch_BoundAlgorithm::Branch_BoundAlgorithm(int task_id, int nr_items, int max_load, Item **items)
  : SearchAlgorithm( task_id ) {
  // Parameters
  Branch_BoundAlgorithm::task_id  = task_id;
  Branch_BoundAlgorithm::nr_items = nr_items;
  Branch_BoundAlgorithm::max_load = max_load;
  Branch_BoundAlgorithm::items    = items;
  // Init other fields
  config 	= new bool[nr_items];
  for (int i = 0; i<nr_items; i++) { config[i] = false;  }//initialise
  best_config 	= new bool[nr_items];
  solution_cost	= 0;
  load 		= 0;
  cost		= 0;
  index		= 0;
  //ADDED-beg (for B&B)
  accumulated_costs = new int[nr_items];
  int sum = 0;
  for (int i = nr_items-1; i > -1; i--) {
    sum += items[i]->cost;
    accumulated_costs[i] = sum;
  }//for all items
  //ADDED-end
} // constructor

Branch_BoundAlgorithm::~Branch_BoundAlgorithm(){
  delete [] items;
  delete [] config;
  delete [] best_config;
  delete [] accumulated_costs;	//ADDED for B&B
} //destructor

// *************************************************************** DESCEND

/** SOLVE the problem by brute force + prune "suboptimal" branches (bound)
 *  The approach:
 *  + We have to try all possible configurations (for which load <= max_load).
 *	A configuration is represented as an array of booleans called config;
 *	if config[i]==true => i-th item is in the solution (in the knapsack).
 *	Thus we have to try all possible bit strings of the length equal to 
 *	the number of items.
 *	We start to set values in the string from the beginning (func. descend), 
 *	when the end is reached, we return to the nearest included item, exclude 
 *	it and set again the rest of the string (from the item to the end; func.
 *	mount()).
 *	BOUND: exclude the item only if the max. reachable cost doesn't become
 *	smaller than the best solution's cost found so far.
 *  The first configuration tried is all ones (if max_load large enough),
 *	the last one all zeros.(Descend creates 1s, mount always adds a 0.)
 */
void Branch_BoundAlgorithm::solve(void){
  // Following shared variables (class fields) are used:
  // index;  load, cost, config; best_config, solution_cost;
  // Fields nr_items and max_load are used as constants here and
  // they are initiated in the constructor.
  index = load = cost = solution_cost = 0;	// re-initiate non-pointer variables
  bool cont = true;
  while (cont) {
    descend();
    cont = mount();
  }//while not done
}// solve

/** DESCEND
 *  D. moves forward in the config[] array to the end.
 *  It always sets config[i] to true, unless the max_load would be exceeded.
 *  Before it finishes, it compares the current (complete) configuration 
 *  with the best one and saves it if it's better.
 */
void Branch_BoundAlgorithm::descend(void){
  // Descend from the current item to the last item (its index is nr_items-1).
  for(; index < nr_items; index++) {
    // Increment the number of steps to the solution
    nr_steps++;

    // Check if we can include the current item (don't exceed max_load)
    // B&B: - only if not already included
    if( (( load + items[index]->weight ) <= max_load) && (!config[index]) ){ // include
      config[index] = true;		// include the item
      load += items[index]->weight;	// add its weight to the total load
      cost += items[index]->cost;  	// add its cost to the total one
    } else if ( lessThanBest(index, cost) ){				    // not excludable
      return;		// there's no sense in descending this branch
    }//if-elsif

  }//for: while not in a leaf

  // Decrement index again, now it's invalid, for it equals to nr_items.
  index--;

  // Compare the current configuration to the best one and perhaps replace it.
  if( cost > solution_cost ){
    solution_cost = cost;		// save the new best cost
    // save the configuration
    for(int i=0; i < nr_items; i++){
      best_config[i] = config[i];
    }//for
  }// compare with the best known solution so far

} // descend

/** MOUNT
 *  Moves backward in the config[] array until config[i]==true found,
 *  set it to false (exlcude it) and finish. Descend will start at config[i+1].
 *  @return false if cannot mount => we are done
 */
bool Branch_BoundAlgorithm::mount(void){
  bool reached1 = false;

  // exclude the last item visited by descend() if included
  if ( config[index] ){
    config[index] = false;	
    load -= items[index]->weight;
    cost -= items[index]->cost;
  }// if 1st item included

  // Mount until an included item found or the beginning of config[] reached.
  // B&B: mount until an included item that *satisfies an exclude condition* is found or ...
  while( (!reached1) && (index > 0) ){
    // This must be first to mount from a leaf (that's where mount is called from)
    // The config. with the leaf excluded doesn't need to be tested, because it
    // can be only worse (by decreasing cost).
    index--;

    // Increment the number of steps to the solution
    nr_steps++;

    // If the current item is included, exclude it, inc. index and finish.
    // B&B test for items that cannot be excluded comes here:
    // The value = cost of included preceding items + cost of all following items
    if ( (config[index])  ) {
      // If excluding this item decreases the max. reachable cost below the value of the best cost so far
      // we continue mounting.
      // The item must be anyway excluded, we only go on mounting.
      if ( !do_notExclude(index) ){
	reached1      = true;	 // say we are done here
      }
      // This item won't be excluded at the beginning of this while loop
      // => do it now
      config[index] = false;	// exclude the item
      load -= items[index]->weight;
      cost -= items[index]->cost;
    }// it the current item is included

  }//while not an included item found or can't mount more

  // descend 1 item, otherwise it would be included again be descend()
  index++;

  return reached1;
} // mount

// ****************************************************************** printResult
void Branch_BoundAlgorithm::printAnyResult(ostream &str) {
  assert( items!=0 );
  str << task_id << " "<< nr_items <<" " << setw(4) << setiosflags(ios::left)<< solution_cost;
  for(int i=0; i<nr_items; i++ ){
    //    if( best_config[i] )
    str <<" "<< best_config[i];
  }//for
  str << endl;
}//printResult

// ******************************************************************** MAIN
// ******************************************************************** MAIN
//
// DEPRECATED and out of date; see main.cc
//
// int main(int argc, char **argv){
//   //Open data file and load the 1st task
//   if ( argc != 2 ) {
//     cout << "Error: Wrong number of parameters.\n";
//     cout << "Use: bruteforce taskfile\n"; 
//   }// if wrong input
//   KnapsackInput *in = new KnapsackInput( argv[1] );

//   // For all tasks in the file:
//   do {
//     // Solve a task
//     Branch_BoundAlgorithm *problem = new Branch_BoundAlgorithm(in->getTaskID(), in->getNr_items(), in->getMax_load(), in->getItems() );
//     problem->solve();
//     problem->printResult();
//   } while ( in->loadNextTask() );
//   //---------
//   return 0;
// }// main