hi guys i really wish if some one could help me with this problem , well i solved it but the output is always wrong so can some one help me:
the Question is in this link:
http://people.westminstercollege.edu/faculty/ggagne/fall2006/306/handouts/hw2/index.html
can some one please help me with the dynamic programing part of the question
this is what i did so far:
---------------------------------
#include <iostream>
using namespace::std;
const int q1=4;
const int q2=4;
double Array[q1][q2]={16,5,4,6,2,5,1,9,8,7,6,5,4,3,2,1};//global variable
double Array2[q1][q2]={16,5,4,6,2,5,1,9,8,7,6,5,4,3,2,1};
//-------Class Object----------
class Object
{
public:
double cost;
int i,j;
};
//-------------------------------
//-----------fuction smallest , return the value of smallest element-------
double smalest(Object A,Object B,Object C)
{
double min;
min=A.cost;
Array2[A.i][A.j]=-1;
if(min>B.cost)
{ Array2[A.i][A.j]=Array[A.i][A.j];
min=B.cost;
Array2[B.i][B.j]=-1;
}
if(min>C.cost)
{ cout<<"in C loop "<<min<<"\n";
Array2[B.i][B.j]=Array[B.i][B.j];
Array2[A.i][A.j]=Array[A.i][A.j];
min=C.cost;
Array2[C.i][C.j]=-1;
}
return min;
}
//---------------------------------------------------------------------------
//------------------function shortest find the shortest path ---------------
Object shortest(int i,int j,int Jmax)
{
if(j>Jmax || i<0 ||i>=q1 )
{Object noValue;
noValue.cost=100000;
return noValue;
}
if(j==Jmax)
{Object temp;
temp.cost=Array[i][j];
temp.i=i;
temp.j=j;
return temp;
}
else
{
Object value;
value.cost= smalest(shortest(i,j+1,Jmax),shortest(i+1,j+1,Jmax ),shortest(i-1,j+1,Jmax))+Array[i][j];
value.i=i;
value.j=j;
return value;}
}
//--------------------------------------------------------------------------------
int main()
{
Object cost;
cost =shortest(1,0,3);
cout<<cost.cost<<"\n";
for (int i=0;i<q1;i++)
{
for (int j=0;j<q2;j++)
cout<<Array2[i][j]<<" ";
cout<<"\n";
}
cout<<"\n";
for ( i=0;i<q1;i++)
{
for (int j=0;j<q2;j++)
cout<<Array[i][j]<<" ";
cout<<"\n";
}
return 0;}
-----------------------------
i hope some one could help me or just post the algorithem
thank all , i will appreciates any attempt