/****************************************************************
 *      Program Solving the KNAPSACK problem using a heurustic  *
 *      Author Jakub Holy                                       *
 *      For the subject PAA, LS2002                             *
 ****************************************************************
 */
//  	$Id: heuristic2.cc.html,v 1.1.1.1 2003/11/08 13:19:49 aja Exp $	


using namespace std;
#include <iomanip>
#include <algorithm>
#include "heuristic2.hh"

// --------------------------------------------- CONST etc.
  HeurItem::HeurItem(int id, Item& it) : Item (it.weight, it.cost){
  HeurItem::id = id;
  ratio        = it.cost / it.weight;
}//HeurItem constr
// ----------------------------------------------------------
HeuristicAlgorithm::HeuristicAlgorithm (int task_id, int nr_items, int max_load, Item **items)
  : SearchAlgorithm( task_id ) {
  // Parameters
  HeuristicAlgorithm::task_id  = task_id;
  HeuristicAlgorithm::nr_items = nr_items;
  HeuristicAlgorithm::max_load = max_load;
  HeuristicAlgorithm::items    = items;

  // Init other fields
  solution 	= new bool[nr_items];	// normally shall be init. to false manually ...
  load 		= 0;
  solution_cost	= 0;

  // The Vector
  //  1. Init the vector: insert items
  for(int i=0; i < nr_items; i++){
    item_vect.push_back( *(new HeurItem(i, *(items[i]))));
  }// items -> item_vect

  //  2. Sort the items
  sort(item_vect.begin(), item_vect.end(), OptimalityCriterium() );
} // constructor

HeuristicAlgorithm::~HeuristicAlgorithm(){
  delete [] items;
  delete [] solution;
} //destructor

// --------------------------------------------- SOLVE
void HeuristicAlgorithm::solve(void){
  for (TItem_vect::iterator iter = item_vect.begin(); iter != item_vect.end(); ++iter) {
    // Increment the number of steps to the solution
    nr_steps++;

    // Include the item, if not too heavy.
    if( ( load + iter->weight ) <= max_load ){
      solution[iter->id] = true;	// include the item; HeurItem:id is its order number in the input file
      load += iter->weight;		// add its weight to the total load
      solution_cost += iter->cost;  		// add its cost to the total one
    } else {
      solution[iter->id] = false;
    }//if-else

  }// for all elements in the vector

  //ADDED for the 3rd homework
  // Check whether the solution "only the most expensive item"
  // isn't better. If yes use it instead.
  {
    // find the most expensive item that is not heavier than max_load 
    TItem_vect::iterator maximum = max_element( item_vect.begin(), item_vect.end(), cmp_cost(max_load) );

    // Compare the solutions
    if( solution_cost < maximum->cost ){
      for(int i=0; i<nr_items; i++){ solution[i] = false;}	// exclude all items
      solution[maximum->id] = true;				// include the most expensive item found
    }// if the solution is worse than "most expensive only"
  }// compare heuristic and "only the most expensive"
  //ADDED-end

}//solve

//--------------------------------------------- PRINT
void HeuristicAlgorithm::printAnyResult(ostream &str) {
  assert( solution!=0 );
  str << solution_cost <<endl;
}//printAnyResult

//****************************************************************** MAIN

// DEPRECATED and out of date

//  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
//     KnapsackProblem *problem = new KnapsackProblem(in->getTaskID(), in->getNr_items(), in->getMax_load(), in->getItems() );
//     problem->solve();
//     problem->printResult();
//   } while ( in->loadNextTask() );
//   //---------
//   return 0;
//  }// main