Dynamic Programming Maximum Profit for Movers in 2 cities

Question

There is a moving company. It operates in two cities. They wish to maximize profit. Given are 2 arrays representing the two cities. The value at position i in each of the arrays indicates the maximum profit to be made in the city that day. If they work in city A on day i, and city B on day i+1, there is a cost associated with travelling between the 2 cities c. We need to use Dynamic Programming to find the maximum profit to be made. Here is an example:

A = {10, 20, 30}
B = {-10, 50, 20}
c = 20
optimal solution = (10 + (50 - 20) + 20) = 10 + 30 + 20 = 60

I think this is similar to weighted interval schedule OR the subset sum problem (knapsack). Any help is appreciated.

EDIT:

I need to find the recurrence relation(s), time complexity of the algorithm and then prove the correctness. Any ideas?

Answer 1

To represent this problem better,

• Let A be the profit matrix where A[c] is the profit array for city c (c = 0 for the first city, c = 1 for the second, and so on).
• Let P(i, c) be the optimal profit up to and including day i such that the moving company end up in city c on day i.
• Let C(c', c) is the cost of moving from a city c' to a city c.

This setup allows us to generalize the solution to an arbitrary number of cities.

In order to maximize P(i, c), we have to consider all possible cities that the movers could be in on the previous day i-1 and choose the maximal option. These possibilities include the movers being in the same city on the previous day, and moving from another city the previous day while incurring a moving cost. Hence

P(i, c) = max(P(i-1, c), max(P(i-1, c') + C(c', c) for all cities c' != c)) + A[c][i]

The first argument in the outer max (P(i-1, c)) considers the case where the movers were in the same city on the previous day, and the second argument (the inner max) evaluates and maximizes the profits (including moving costs) if the movers were in a different city on the previous day.

The final answer is simply max(P(n, x) for all cities x) where n is the last day (considering all possible cities the movers could end up in on the final day).

In your example, city A == city 0, city B == city 1, profit matrix A = [[10, 20, 30], [-10, 50, 20]], and C(0, 1) = C(1, 0) = 20.

EDIT:

The time complexity will be O(nc), where n is the number of days and c is the number of cities. If the number of cities is fixed, then the time complexity is O(n).

Proving correctness can be done using induction. Assume that P(i-1, x) is maximal for all cities x. Then show that P(i, c) for some city c as defined above is maximal. There are two possibilities for the maximal solution:

• The movers were in the same city c on day i-1
• The movers were in a different city c' on day i-1.

Now all you have to show is that the recurrence defined above will give you the correct solution in both these cases.