There are n trading posts numbered 1 to n as you travel downstream. At any tradi

Question

There are n trading posts numbered 1 to n as you travel downstream. At any trading post i you can rent a canoe to be returned at any of the downstream trading posts j>i. You are given a cost array R(i,j) giving the cost of these rentals for all 1i<jn. We can assume that R(i,i)=0, and that you can't go upriver (so perhaps R(i,j)= if i>j). For example, one cost array with n=4 might be the following.

The problem is to find a dynamic programming algorithm that computes the cheapest sequence of rental taking you from post 1 all the way down to post n. In this example, the cheapest way is to rent canoes from post 1 to post 3, and then from post 3 to post 4 for a total cost of 5. The second problem is to find the least cost associated with this sequence. You are to design a dynamic programming algorithm for both the problems.

Describe the table and what does each entry in the table mean?

How will the table be initialized?

In which order the table will be filled?

What is the recurrence?

How will you use the table to find what is cheapest sequence of canoe rental (for the first problem) and the least cost of the canoe rentals (for the second problem)?

Give the asymptotic complexity of the algorithms. Implement the your algorithm by using C

Input: The input consists of n+1 lines: the first line will be a single integer that indicates the number of trade posts. The next n lines will give the rental costs that taking post i to j (where ij). For example, the input of the above given example would be:

Output: Output the minimum cost to travel from post 1 to post n. Output the sequence of canoe renting that achieves the goal. For example, the sample output of the above given example would be:

Requirements:

Your program is required to support up to 100 posts.

Your program can either take keyboard input or input redirection from a file. For example,

In the readme file, please describe your algorithm design by answering all the questions above. In addition, please provide the commands that compile and run the program. Meanwhile, provide at least one sample run to show your program works.

List the existing bugs in your program.

Explanation / Answer

First we take the number of posts in n. Then we create an nxn cost matrix and take the cost of going from i->j. Now we create an array of size n which is called dp. dp[j] basically tells us the minimum cost needed to travel from post 1 to post j. We also create an array called path of size n. path[j] tells us the last post where we stopped. Now following is the dp relation.

dp[j]=min(dp[j],dp[i]+cost[i][j]) where 0<=i<j;

if the value of dp[j] is updated then correspondingly the path is also updated.

#include <bits/stdc++.h>
using namespace std;

int main(){
   int n;
   cout<<"Enter the number of posts"<<endl;
   cin>>n;
   cout<<"Enter the cost in an nxn array form"<<endl;
   vector<vector<int> > cost(n,vector<int>(n,-1));
   for(int i=0;i<n;i++){
       for(int j=i;j<n;j++){
           cin>>cost[i][j];
       }
   }
   vector<int> dp(n,INT_MAX);
   vector<int> path(n);
   path[0]=-1;
   dp[0]=0;
   for(int j=1;j<n;j++){
       for(int i=0;i<j;i++){
           if(dp[i]+cost[i][j]<dp[j]){
               dp[j]=min(dp[j],dp[i]+cost[i][j]);
               path[j]=i;
           }
       }
   }
   cout<<dp[n-1]<<endl;
   int i=n-1;
   stack<int> s;
   while(path[i]!=-1){
       s.push(i);
       i=path[i];
   }
   s.push(i);
   while(s.size()>1){
       cout<<s.top()+1<<"->";
       s.pop();
   }
   cout<<s.top()+1<<endl;
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.