/*************************************************************
 *      Program Solving the KNAPSACK problem by brute force  *
 *      Author Jakub Holy                                    *
 *      For the subject PAA, LS2002                          *
 *      hw1_force.hh                                         *
 *************************************************************
 */

#include "ksack_in.hh" //# includes Item

/* This class represents the problem and the algorithm to solve it. */
class KnapsackProblem {
private:
  // fields
  int task_id;
  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 best_cost;	// cost of the best_config configuration
  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.

public:
  KnapsackProblem(int task_id, int nr_items, int max_load, Item **items);
  ~KnapsackProblem();
  void solve(void);
  void printResult(void);
}; // KnapsackProblem