Dynamic Programming : Write an Algorithm to Minimize Cost
Not what you're looking for?
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?
Purchase this Solution
Solution Summary
An algorithm that minimizes cost is written.
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, ...
Purchase this Solution
Free BrainMass Quizzes
Multiplying Complex Numbers
This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.
Know Your Linear Equations
Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.
Exponential Expressions
In this quiz, you will have a chance to practice basic terminology of exponential expressions and how to evaluate them.
Solving quadratic inequalities
This quiz test you on how well you are familiar with solving quadratic inequalities.
Geometry - Real Life Application Problems
Understanding of how geometry applies to in real-world contexts