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 1≤i<j≤n. 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.

to j 1 234 1 037 Cost from i 3

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 i≤j). For example, the input of the above given example would be:

4
0 2 3 7
0 2 4
0 2
0

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:

The minimum cost is 5
The renting sequence is 1->3->4

I have an algorithm to find the minimum cost. How could I go about printing the renting sequence?

Answer 1

Description of the table:

The cost table indicates the cost values from one post to another. The entries in the cost table indicates the cost value from the post i to the post j. For example, in the given table, the cost from the post 1 to post 4 is 7.

Initialization of the table:

The table can initialise using 2-dimensional array. The values of the cost from post i to post j can store in the 2-dimensional array. For example, let the 2-dimensional array is postcost[][].

Then, the value of the cost from the post 1 to post 4 is stored as postCost[1][4] =7.

Filling the table:

The values in the table can be filled by taking the post i to j where i value is less than or equal to j (i<=j).

Recurrence: The recurrence has one or more bases cases and recursive cases. The recursive function is sequence of term in a linear combination of the previous terms.

The minimum cost can be find by using the recursion function and checks every path and by finding the sum of the cost of the post of the minimum path using the recursive functions.

Program screenshot:

$# include<stdio.h> //function prototypes int getMiniumcost (int postCost [10] [10]) int findShortestPath (int postCost [10] [10], int source, int destination); //declare the variables int numofTrades; int postCost[10] [10]0 ; //definition of the main int main() //read the number of trade posts. scanf (%d, &nurnOfTrades) ; int i, ji //read the rental costs that taking post i to j (where išj) for (i -0; i < numofTrades; i++) for (j0 j < numofTrades: j++) if (i < j) scanf (%d, &postcost [i] [j]); //call the function getMiniumcost) by passing the postCost array printf (The min. Cost cost is %d\n, getMiniumCost (postcost)); return 0;$

Screenshot of the output:

Code to copy:

#include<stdio.h>

//function prototypes

int getMiniumCost(int postCost[10][10]);

int findShortestPath(int postCost[10][10], int source, int destination);

//declare the variables

int numOfTrades;

int postCost[10][10] = { 0 };

//definition of the main

int main()

{

       //read the number of trade posts.

       scanf("%d", &numOfTrades);

       int i, j;

       //read the rental costs that taking post i to j (where i≤j)

       for (i = 0; i < numOfTrades; i++)

       {

              for (j = 0; j < numOfTrades; j++)

              {

                     if (i <= j)

                     {

                           scanf("%d", &postCost[i][j]);

                     }

              }

       }

       //call the function getMiniumCost() by passing the postCost array

       printf("The minimum cost is %d\n", getMiniumCost(postCost));

       return 0;

}

//definition of the function getMiniumCost()

int getMiniumCost(int postCost[10][10])

{

       //call the function findShortestPath()

       return findShortestPath(postCost, 0, numOfTrades - 1);

}

//definition of the function findShortestPath()

int findShortestPath(int postCost[10][10], int source, int destination)

{

       // if source and destination is same

       if (source == destination || source + 1 == destination)

              return postCost[source][destination];

       int min_Cost = postCost[source][destination];

       //iterate for all the nodes

       for (int i = source + 1; i<destination; i++)

       {

              int temp = findShortestPath(postCost, source, i) + findShortestPath(postCost, i, destination);

              if (temp < min_Cost)

              {

                     min_Cost = temp;

              }

       }

       //return the min_Cost cost

       return min_Cost;

}