There are n trading posts along a river. At any of the posts you can rent a cano

Question

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 from i to j is higher than 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 from each possible departure point i to each possible arrival point j. In terms of n, how much time is needed by your algorithm?

Explanation / Answer

Let A[i, j] represent the cost fo renting a canoe at post i and returning it at post j. There are n subproblems: Let T[1, k] be the cheapest cost of traveling from post 1 to post k, for k = 1 . . . n. Our goal is to find T[1, k], 1 < k n. here is the dynamic program:

T[1, 1] = 0 (for k = 2 to n)

do T[1, k] = minj=1...k1 {T[1, j] + A[j, k]}.

The running time is O(n 2 ).

Similarly, we can find T[2, k], 2 < k n, T[3, k], 3 < k n, . . . , T[n 1, n].

Totaly, the running time is O(n 3 ).

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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