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


using namespace std;

#ifndef _COMMON_H
#include "common.hh"   // class SearchAlgorithm
#endif

#ifndef _KSACK_IN_HH
#include "ksack_in.hh" // input file processing, class Item
#endif

// ------------------------------------------------------------------------------------------- IF
#ifndef _DYNAMIC_PROGR_H

/** This class represents the problem and the algorithm to solve it. 
 *  Algorithm: Dynamic Programming
 **/
class Dynamic_ProgrAlgorithm : public SearchAlgorithm {
  // fields
  int max_load;	     	// the maximum weight the knapsack can carry, i.e. its capacity
  int nr_items;      	// the number of items we have
  Item **items;	     	// an array of items of this problem
public:
  Dynamic_ProgrAlgorithm(int task_id, int nr_items, int max_load, Item **items);
  virtual ~Dynamic_ProgrAlgorithm();		// for gcc not to complain
  virtual void solve(void);
  virtual void printAnyResult(ostream &str);	// not needed, but must be defined for it's abstract
};// SearchAlgorithm

// ------------------------------------------------------------------------------------------- ENDIF
#define _DYNAMIC_PROGR_H
#endif