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


using namespace std;	// necessary to be able to include <vector>
// #include <vector>
// #include <algorithm>

#ifndef _COMMON_H
#include "common.hh"   // class SearchAlgorithm
#endif

#ifndef _KSACK_IN_HH
#include "ksack_in.hh" // input file processing, class Item
#endif

#ifndef _BRANCH_BOUND_HH
#define _BRANCH_BOUND_HH
#endif

/* This class represents the problem and the algorithm to solve it. */
class Branch_BoundAlgorithm : public SearchAlgorithm {
private:
  //ADDED for Branch_BoundAlgorithm (compare to hw1_force.hh)
  int *accumulated_costs;// acc._cost[i] = sum of costs(item i ... last item)
  //ADDED-end
  // fields
  int max_load;	     	// the maximum weight the knapsack can carry
  int nr_items;      	// the number of items we have
  Item **items;	     	// an array of items of this problem
  // A configuration of the algorithm - a (partial) solution.
  // It's an array of booleans, if config[i]== true, then items[i]
  // (i-th item) is inside the knapsack.
  bool *config;
  bool *best_config; 	// the best solution found so far
  int load;		// current load of the knapsack
  int cost;		// cost of the current (partial) configuration
  int index;		// index for config[]

  // methods
  void descend(void);
  bool mount  (void);	// Return false if can't mount => we're done.
  // Return true if the max. reachable cost after excluding the item 
  // is lower than the best cost so far 
  inline bool do_notExclude(int item)
  { return lessThanBest(item, cost - items[item]->cost); }

  // In this state (given by preceding_cost) he item must be included
  inline bool lessThanBest(int item, int preceding_cost)
   { return (preceding_cost + accumulated_costs[item+1]) <  solution_cost; }

public:
  Branch_BoundAlgorithm(int task_id, int nr_items, int max_load, Item **items);
  virtual ~Branch_BoundAlgorithm();		// for gcc not to complain
  virtual void solve(void);
  virtual void printAnyResult(ostream &str);
}; // Branch_BoundAlgorithm