void init_table(My_matrix<double>& t, int nRow, int nCol);
void print_table(My_matrix<double>& t, int nRow, int nCol);
void fill_table(My_matrix<double>& t, int* w,double* v,int n,int cap);
void get_results(My_matrix<double>& t,int* w,double* v);
void print_results(const Triple* results, int rslt_cnt);
extern void my_assert(bool val, char* err_info);
//solving the knapsack problem by dynamic programming technique
//@param
//w - weight
//v - values
//n - n values with corresponding weights
//cap - capacity of the knapsack
void knapsackSolve(int* w,double* v,int n,int cap)
{
Triple* results = NULL;
int rslt_cnt = 0;
My_matrix<double> table(n+1,cap+1); //the row number is n+1 because the Knapsack Problem
// dynamic programming table requires n+1 rows;
// so is the column number
init_table(table,n+1,cap+1);
fill_table(table,w,v,n,cap);
print_table(table,n+1,cap+1);
get_results(table,w,v);
// cout<<"result count: "<<rslt_cnt<<endl;
//cout<<"results[0]: "<<results[0].no<<endl;
//print_results(results,rslt_cnt);
}//end of knapsackSolve
void init_table(My_matrix<double>& t, int nRow, int nCol)
{
for(int i=0;i<nRow;i++)
for(int j=0;j<nCol; j++)
{
if(j==0||i==0)
t.setElement(i,j, 0);
else
t.setElement(i,j, -1);
}
}//end of init_table
void fill_table(My_matrix<double>& t, int* w,double* v,int n,int cap)
{
my_assert(t.getColCnt() == cap+1,
"Cannot fill the table: The column number of the table is invalid.");
my_assert(t.getRowCnt() == n+1,
"Cannot fill the table: The row number of the table is invalid.");
my_assert(n > 0 && cap > 0 && w != NULL && v != NULL,
"Invalid parameter in function: void fill_table(...)");
//filling the table using dynamic programming recurrence:
//V[i,j] = max{V[i-1,j],v[i-1] + V[i-1,j-w[i-1]]}; if j-w[i-1] >= 0
//V[i,j] = V[i-1,j]; if j-w[i-1] < 0
for(int i = 1; i < n+1; ++i)
{
for(int j = 1; j < cap+1; ++j)
{
if(j-w[i-1] >= 0)
{
double e1 = t.elementAt(i-1,j);
double e2 = t.elementAt(i-1,j-w[i-1]) + v[i-1];
double max = (e1 > e2)? e1 : e2;
t.setElement(i,j,max);
}
else
{
t.setElement(i,j,t.elementAt(i-1,j)); // V[i,j] = V[i-1,j]
}
}
}
}//end of fill_table(...)
void print_table(My_matrix<double>& t, int nRow, int nCol)
{
cout<<"Printing dynamic Table: "<<nRow<<" rows, "<<nCol<<" Columns"<<endl;
for(int i=0;i<nRow;i++)
{
for(int j=0;j<nCol;j++)
{
cout<<(t.elementAt(i,j))<<" ";
}
cout<<endl;
}
cout<<endl;
}// end of void print_table(...)
void get_results(My_matrix<double>& t, int* w,double* v)
{
Triple* temp = new Triple[t.getRowCnt()];
int rslt_cnt = 0;
int i = t.getRowCnt() - 1; //row flag
int j = t.getColCnt() - 1; //column flag
while(i > 0 && j > 0)
{
if(t.elementAt(i,j) != t.elementAt(i-1,j))
{
//add the ith item to the results
temp[rslt_cnt].no = i;
temp[rslt_cnt].value = v[i-1];
temp[rslt_cnt].weight= w[i-1];
++rslt_cnt;
j = j-w[i-1];
}
--i;
}
print_results(temp,rslt_cnt);
if(temp != NULL)
{
delete [] temp;
}
return ;
}//end of void get_results(...)
void print_results(const Triple* results, int rslt_cnt)
{
cout<<"No. Value Weight"<<endl;
for(int i =0; i<rslt_cnt; ++i)
{
//cout<<"Inside the loop: i="<<i<<endl;
cout<<results[i].no<<" "
<<results[i].value<<" "<<results[i].weight
<<endl;
}
}//end of void print_results(...);
void test_dp()
{
int n = 4;
int cap = 5;
int w[]={2,1,3,2};
double v[]={12,10,20,15};
// My_matrix<double> table(n+1,cap+1);
// init_table(table,n+1,cap+1);
// fill_table(table,w,v,n,cap);
// print_table(table,n+1,cap+1);
knapsackSolve(w,v,n,cap);
}//end of void test_dp()
// if val == false, err_info will be printed, and the program exits.
void my_assert(bool val, char* err_info)
{
if(!val)
{
cout<<err_info<<endl;
exit(0);
}
}
/*
* My_matrix.cpp
*
* Created on: Jul 11, 2010
* Author: kevin
*/
#include <iostream>
#include <stdlib.h>
#include "My_matrix.h"
using namespace std;
extern void my_assert(bool val, char* err_info);
template<class T>
My_matrix<T>::My_matrix(int nRow, int nCol)
{
my_assert(nRow > 0,
"Invalid Row number in constructing My_matrix");
my_assert(nCol > 0,
"Invalid Column number in constructing My_matrix");
arr = new T*[nRow];
for(int i=0;i<nRow;i++)
{
arr[i] = new T[nCol];
}
//initialize all the elements with NULL
for(int i=0;i<nRow;i++)
for(int j=0;j<nCol;j++)
arr[i][j] = NULL;
this->nCol = nCol;
this->nRow = nRow;
}
template<class T>
My_matrix<T>::~My_matrix(void)
{
if(arr != NULL)
{
for(int i=0;i<nRow;i++)
{
if(arr[i] != NULL)
delete[] arr[i];
}
}
delete []arr;
}
template<class T>
T& My_matrix<T>::elementAt(int row, int col)
{
my_assert(row >= 0 && row < nRow,
"Invalid Row number in My_matrix<T>::elementAt(int,int)");
my_assert(col >= 0 && col < nCol,
"Invalid Column number in My_matrix<T>::elementAt(int,int)");
return arr[row][col];
}
template<class T>
void My_matrix<T>::setElement(int row, int col, const T& val)
{
my_assert(row >= 0 && row < nRow,
"Invalid Row number in My_matrix<T>::setElement(int,int,T)");
my_assert(col >= 0 && col < nCol,
"Invalid Column number in My_matrix<T>::setElement(int,int,T)");
arr[row][col] = val;
}
template<class T>
int My_matrix<T>::getRowCnt(void)const
{
return nRow;
}
template<class T>
int My_matrix<T>::getColCnt(void)const
{
return nCol;
}
//template<class T>
//void print_my_matrix(const My_matrix<T>& m)
//{
// int r = m.getRowCnt();
// int c = m.getColCnt();
//
// for(int i=0;i<r;i++)
// {
// for(int j=0;j<c;j++)
// cout<<m.elementAt(i,j)<<" ";
//
// cout<<endl;
// }
//}
void test_my_matrix()
{
int r = 8;
int c = 4;
My_matrix<double> m(r,c);
cout<<"Row cnt: "<<m.getRowCnt()<<endl;
cout<<"Col cnt: "<<m.getColCnt()<<endl;
for(int i=0;i<r;i++)
for(int j=0;j<c;j++)
m.setElement(i,j,(double)(i+j));
//print_my_matrix(m);
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
cout<<m.elementAt(i,j)<<" ";
cout<<endl;
}
}
extern void test_dp();
extern void test_Array();
extern void test_my_matrix();
//extern void test_2D_Array();
int main() {
//cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!!
//test_Array();
test_dp();
//test_my_matrix();
return 0;
}