/****************************************************************
 *								*
 *      Program Solving the KNAPSACK problem (task 3)  		*
 *	 using Dynamic Programming				*
 *      Author Jakub Holy                                       *
 *      For the subject PAA, LS2002                             *
 *	dynamic_progr.cc					*
 *								*
 ****************************************************************
 */


using namespace std;

#include <algorithm>		// fill(), copy
#include <iterator>		// ostream_iterator
#include <vector>

#include "dynamic_progr.hh"

Dynamic_ProgrAlgorithm::Dynamic_ProgrAlgorithm(int task_id, int nr_items, int max_load, Item **items)
  : SearchAlgorithm( task_id ) {
  // Parameters
  Dynamic_ProgrAlgorithm::task_id  = task_id;
  Dynamic_ProgrAlgorithm::nr_items = nr_items;
  Dynamic_ProgrAlgorithm::max_load = max_load;
  Dynamic_ProgrAlgorithm::items    = items;
}// Dynamic_ProgrAlgorithm

Dynamic_ProgrAlgorithm::~Dynamic_ProgrAlgorithm(){
  delete [] items;
  //  delete [] config;
} //destructor

/** Return maximum */
inline int max(int i1, int i2){
  return (i1 > i2)? i1 : i2;
}//max

/** Solve the problem
 *  To be able to apply Dynamic Programming (DP) to solve a problem
 *  it must satisfy "Principle of optimality": it must hold that
 *  no matter what the first decision is, the remaining decisions
 *  are optimal with respect to the state that results from this
 *  decision.
 *  Inversed knapsack problem: select items in such a way that 
 *  the sum of their weights is equal to a given number W and
 *  at the same time the sum of their costs is as high as possible.
 *  For this problem it holds, that having an optimal solution
 *  consisting of the things {T1, T2, ..., Tn}, if we remove 
 *  a thing Ti and decrease W by its weight than 
 *  {T1, T2, ..., Ti-1, Ti+1, ..., Tn} IS an optimal solution
 *  of this problem. Thus DP may be applied.
 *  To solve the ordinary 0/1 knapsack problem, we solve
 *  the inversed problem for all total weights W in the range
 *  0 ... max.load (= capacity of the knapsack) and select the one 
 *  that satisfies the condition of maximal load and has the maximal 
 *  total cost.
 */
void Dynamic_ProgrAlgorithm::solve(void){
  // Array of best costs reached so far for a given capacity
  // After i-th loop there're best results for k <= i first items.
  vector<int> bestcosts (max_load);

  // Init ---
   fill( bestcosts.begin(), bestcosts.end(), 0 );

  // Compute ---
  // Loop over first i items
  for (int i = 0; i < nr_items; i++){

    // Loop over all weights <= maximal load (over all smaller knapsacks)
    /* w must be decreased otherwise in max(2nd argument) we would consider
     * solution for i items instead of i-1 items which is correct; thus
     * to the left from w there must be solutions from the previous
     * execution of the main loop (i-1) and to the right there are
     * solutions for this execution (i).*/
    for (int w = max_load; w > 0; --w){
      // Increment the number of steps performed so far
      nr_steps++;
      // Can the item be part of this solution? (Is it lighter then the current bound?)
      if (items[i]->weight < w) {
	// Effectively, bestcosts[w] = MAXIMUM of:
	//    1. best solution for k < i first items and capacity w, without i-th item, 
	//    2. best solution for k = i first items and capacity w, including i-th item
	//       (which is based on the best solution for k < i and capacity (w - i-th item's weight))
	bestcosts[w] = max( bestcosts[w], bestcosts[w - items[i]->weight] + items[i]->cost );      
      }// 
    }// for all weights
  }// for all items
  //The solution is in bestcosts[max_load]; (even if the solution total weight < max_load)
  solution_cost = bestcosts[max_load];
}// solve

// ****************************************************************** printResult
// Must be defined for it's abstract in the parent class, but it is not
// needed here.
void Dynamic_ProgrAlgorithm::printAnyResult(ostream &str) { printResult(str); }//printAnyResult

//     //DEBUG: printout
//     cout <<"Solve: bestcost["<<i<<"] is:";
//     copy (bestcosts, bestcosts+max_load,
//       ostream_iterator<int> (cout, " ")); 
//     cout << endl;
//     //DEBUG-end