code in C++ Instructor: Dr. Natarajan Meghanathan Project 5: Dynamic Programming
ID: 3739586 • Letter: C
Question
code in C++
Instructor: Dr. Natarajan Meghanathan Project 5: Dynamic Programming Algorithm for Optimum Coin Collection in a Two- Dimensional Grid Due: March 29th, 1 PM (Submission through Canvas) In this project, you will extend the dynamic programming algorithm that we discussed in class for the Coin Collection problem in a two-dimensional grid and implement the same. The conditions for the robot movement are as follows: at any time, the robot can move one cell down or one cell to the right One cell down One cell to the right Each of you are assigned a grid of dimensions n (rows) x m (columns) as specified in the next page. You are required to randomly distribute P number of coins (where PExplanation / Answer
#include<iostream>
#include<cstdlib>
using namespace std;
class maxcoin{
int nrow,ncol;
int **matrix;
int *row,*col,*path;
int P,V;
public:
maxcoin(int r, int c,int p, int v)
{
int i,j;
P=p;
V=v;
nrow=r;ncol=c;
matrix=new int*[r];
for(i=0;i<r;i++)
matrix[i]=new int[c];
row=new int[r*3];
col=new int[r*3];
path=new int[r*c*3];
for(i=0;i<r;i++)
for(j=0;j<c;j++)
matrix[i][j]=0;
}
void getcoin()
{
int i, j,k=0;
cout<<"Eneter the coins of Matrix"<<nrow<<"X"<<ncol<<endl;
while(k!=P)
{
i=rand()%nrow;
j=rand()%ncol;
if(matrix[i][j]==0)
{
matrix[i][j]=(rand()%V)+1;
k++;
}
}
cout<<" Distribution of Coin Values: ";
for(i=0;i<nrow;i++)
{
for(j=0;j<ncol;j++)
cout<<matrix[i][j]<<" ";
cout<<endl;
}
}
void dptable()
{
int i,j;
for(i=1;i<nrow;i++)
matrix[i][0]+=matrix[i-1][0];
for(i=1;i<ncol;i++)
matrix[0][i]+=matrix[0][i-1];
for(i=1;i<nrow;i++)
for(j=1;j<ncol;j++)
if(matrix[i-1][j]>matrix[i][j-1])
matrix[i][j]+=matrix[i-1][j];
else
matrix[i][j]+=matrix[i][j-1];
cout<<" Dynamic programming Table: ";
for(i=0;i<nrow;i++)
{
for(j=0;j<ncol;j++)
cout<<matrix[i][j]<<" ";
cout<<endl;
}
}
void coinselection()
{
int i=0,j=0,nr=0,nc=0,tc=0;
path[tc++]=0;
path[tc++]=0;
while(i<nrow&&j<ncol)
{
if(i==nrow -1)
{
while(++j<ncol)
{
path[tc++]=row[nr++]=i;
path[tc++]=row[nr++]=j;
}
break;
}
else
if(j==ncol-1)
{
while(++i<nrow)
{
path[tc++]=col[nc++]=i;
path[tc++]=col[nc++]=j;
}
break;
}
else
if(matrix[i+1][j]>=matrix[i][j+1])
{
path[tc++]=col[nc++]=i+1;
path[tc++]=col[nc++]=j;
i++;
}
else
{
path[tc++]=row[nr++]=i;
path[tc++]=row[nr++]=j+1;
j++;
}
}
cout<<" Path Traveresed: ";
for(i=0;i<tc;i++)
{
cout<<path[i]<<" ";
if((i+1)%2==0&&(i+1)<tc)
cout<<",";
}
cout<<" Number of horizontal Movement: ";
for(i=0;i<tc-2;i+=2)
{
if(path[i]==path[i+2])
cout<<" "<<path[i]<<" "<<path[i+1]<<"->"<<path[i+2]<<" "<<path[i+3];
}
cout<<" Number of Vertical Movement:"<<" ";
for(i=1;i<tc-2;i+=2)
{
if(path[i]==path[i+2])
cout<<" "<<path[i-1]<<" "<<path[i]<<"->"<<path[i+1]<<" "<<path[i+2];
}
}
};
int main()
{
int r,c,p,v;
cout<<"Enter the no. of row :";
cin>>r;
cout<<" Enter the no. of column :";
cin>>c;
cout<<" Enter the no. of coin :";
cin>>p;
cout<<" Enter the maximum value of coin :";
cin>>v;
maxcoin coin(r,c,p,v);
coin.getcoin();
coin.dptable();
coin.coinselection();
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.