Explore BrainMass

Dynamic Programming : Write an Algorithm to Minimize Cost

This content was STOLEN 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 October 24, 2018, 6:58 pm ad1c9bdddf

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.

See Also This Related BrainMass Solution

Critically evaluate: Historic cost or alternative measurement base

Historic cost should be replaced by an alternative measurement base in order to make financial statement more useful.
Critically discuss this statement, concluding with whether or not you agree with it.

Consider the following:

Critically discuss the role and relevance of financial accounting information to the principal stakeholders in the business.
Appraise the limitation of financial accounting as a system of reporting business performance
Communicate financial information and concept.
Some description and explanation is needed but you need to develop arguments and discussion.
You are expected to take a critical perspective, for example recognize the limitations of certain measurement bases.

Referred to: Information for Better Markets: Measurement in Financial Reporting (Institute of Chartered Accountants in England and Wales) icaew.com/bettermarkets

View Full Posting Details