/****************************************************************
 *      Program Solving the KNAPSACK problem using a heurustic  *
 *      Author Jakub Holy                                       *
 *      For the subject PAA, LS2002                             *
 *      ---							*
 *      Based on hw1_heuristic.hh from the 1st homework         *
 *	Changes:						*
 *	- result compared to "the most worth thing only"	*
 *	  and the better one becomes the result			*
 *	- vector.h, algo.h replaced by vector, algorithm	*
 *      - The class renamed: 					*
 *		KnapsackProblem => HeuristicAlgorithm		*
 *		and made a child of SearchAlgorithm		*
 ****************************************************************
 */

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" //# includes Item
#endif

class HeurItem: public Item {
public:
  double ratio;
  int id;
  HeurItem(int id, Item&);
};//HeurItem

/** Needed for sorting
 *  Criterium: the biggest rate cost/weight the better
 */
struct OptimalityCriterium {  
  // return true, if the 1st param shall be placed before the 2nd one
  bool operator()(const HeurItem& a, const HeurItem& b) {
    return a.ratio > b.ratio;
  }
};//OptimalityCriterium

// Vector of Item
typedef vector<HeurItem> TItem_vect;

/** Needed to find the most expensive element (that is not too heavy)
 */
struct cmp_cost { 
  int max_weight;
  bool operator()(const HeurItem& a, const HeurItem& b) const{ 
    return ( a.cost<b.cost )&&( b.weight<=max_weight );}
  cmp_cost(int max_load){ max_weight = max_load; }
};

// ------------------------------
/** Solve the knapsack problem by a heuristic
 *  Heuristic: order the items w.r.t. the ratio cost/weight
 *  and starting from the 1st ordered item, insert it into 
 *  the knapsack unless the max. load (capacity) is exceeded.
 *  
 *  Compare the solution with "the highest-cost item only"
 *  and take the better one.
 */
class HeuristicAlgorithm : public SearchAlgorithm {
private:
  // 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
  bool *solution;
  TItem_vect item_vect; // vector of sorted items
  OptimalityCriterium optimality; // for sorting
  int load;		// total load of the items in a solution

public:
  HeuristicAlgorithm(int task_id, int nr_items, int max_load, Item **items);
  virtual ~HeuristicAlgorithm();	// virtual to make gcc happy
  virtual void solve(void);
  virtual void printAnyResult(ostream &str);
}; // HeuristicAlgorithm