*      Program Solving the KNAPSACK problem using a heurustic  *
 *      Author Jakub Holy                                       *
 *      For the subject PAA, LS2002                             *

#include <vector.h>
#include <algo.h>
#include "ksack_in.hh" //# includes Item

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

/** 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;

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

// ------------------------------
class KnapsackProblem {
  // 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
  bool *solution;
  TItem_vect item_vect; // vector of sorted items
  OptimalityCriterium optimality; // for sorting
  int load;		// total load of the items in a solution
  int cost;		// cost of the solution

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