Explore BrainMass

# Dynamic Programming : Write an Algorithm to Minimize Cost

Not what you're looking for? Search our solutions OR ask your own Custom question.

This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

There are n trading posts along a river. At any of the posts you can rent a canoe to be returned at any other post downstream. (It is next to impossible to paddle against the current.) For each possible departure point i and each possible arrival point j the cost of a rental from i to j is known. However, it can happen that the cost of renting for i to j is higher that the total cost of a series of shorter rentals. In this case you can return the first canoe at some post k between i and j and continue your journey in a second canoe. There is no extra charge for changing canoes in this way.

Give an efficient algorithm to determine the minimum cost of a trip by canoe for each possible departure point i to each possible arrival point j. In terms of n, how much time is needed by your algorithm?

Â© BrainMass Inc. brainmass.com November 30, 2021, 12:40 am ad1c9bdddf
https://brainmass.com/math/discrete-math/dynamic-programming-write-an-algorithm-to-minimize-cost-54287

#### Solution Preview

Let c(i,j) be the cost of a rental directly from i to j. From the condition, it is impossible to paddle against the current. So we always assume i<=j in c(i,j). Moreover, c(i,i)=0.
Suppose the function MinCost(i,j) outputs the minimum cost of a trip by canoe from i to j with (i<=j). We know, ...

#### Solution Summary

An algorithm that minimizes cost is written.

\$2.49