/***************************************************************************
 ***   FILE: knapsack_recursion.cpp
 ***   DATE: 11/01/2003
 *** AUTHOR: Daniel Dementiev
 ***  DESCR: This is an example program for IST238:Algorihms class.
 ***         This programm illustrates the simple recursion solution
 ***         of the knapsack prblem. The recursion algorithm is implemented
 ***         in the knapsack() function. This function takes three arguments:
 ***          - an array of items
 ***          - the number of items
 ***          - the limit weight
 ***         This function returns an integer number - the sum value of the
 ***         selected items.
 ***         To execute this program you can use:
 ***         ...> knapsack_recursion
 ***         ...> knapsack_recursion <number_of_items>
 ***         ...> knapsack_recursion <number_of_items> <boundary_weight>
 ***         All the items will be generated rendomly.
 ***************************************************************************/

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>
using namespace std;
#include <windows.h>


// New type that contains all information about an item
struct TItem {
   int  price;
   int  weight;
};

void print_items(TItem *items, int size)
{
   cout<<"      #     w   $$$\n";
   for(int i=0;i<size;i++)
      cout<<"Item "<<setw(3)<<i<<": "
          <<setw(4)<<items[i].weight
          <<setw(6)<<items[i].price<<endl;
}

// -------------------------------------
// Recursion version
int knapsack(TItem *items, int n, int weight)
{
   if( n==0 || weight<=0 ) return 0;
   int sub_price = knapsack(items, n-1, weight);
   if( items[n-1].weight > weight )
      return sub_price;
   int max_price = items[n-1].price + knapsack(items, n-1, weight-items[n-1].weight);
   if( max_price < sub_price ) max_price = sub_price;
   return max_price;
}

// =============================================


void main(int argc, char *argv[])
{
   int    N, W, totalw=0, price;
   TItem *items;

   N = argc>1 && (N=atoi(argv[1])) ? N : 10;
   W = argc>2 && (W=atoi(argv[2])) ? W : 0;

   cerr<<"Generating a random knapsack problem of the size "<<N<<" ...";
   items = new TItem[N];
   srand((unsigned)time(NULL));
   for(int i=0;i<N;i++){
      items[i].price = 5 + rand() % (2*N);
      items[i].weight = 3 + rand() % N;
      totalw += items[i].weight;
   }
   W = W>0 ? W : totalw/3;
   cerr<<"\b\b\b[Done]\n";
   print_items(items, N);
   cout<<"Knapsack can contain up to "<<W<<" pounds\n";

   // dynamic progr. version
	DWORD runtime = GetTickCount();
   price = knapsack(items, N, W);
	runtime = GetTickCount() - runtime;
	cout<<"\n\nRecursion version runtime is "<<runtime<<" msec\n";
   cout<<"The max price found by the recursion method is $"<<price<<endl;
}