dynamic programming question similar to traveling salesman in python

Question

So I just started exploring dynamic programming a little bit more in depth and I have come across a question which I've been unable to solve for a while now. I would greatly appreciate any help with it.

Find the maximum revenue for a salesman who knows how much revenue he will get in each city per day, given he is free for len(days_travel) days;

The input list revenue shows the revenue he will get on a particular day at a particular city (eg. revenue[0][1] = 2: day 0 and at city 'b') and travel days is the number of days he requires to travel from one city to the other (eg. days_travel[2][1] = 2 days is required to move from city c to city b and start is the city he starts in (at day 0)

Answer 1

Edit:

After doing tests I found that the code did not work perfectly I came to the conclusion that the required efficiency is O(n^3 * d^2) which is super inefficient.

My code is a sufficient compromise with an efficiency of O(n * d^2)

The final code:

        def floyd_warshall_days(days_travel):

    nV = len(days_travel)
    G = days_travel
    # Adding vertices individually
    for k in range(nV):
        for i in range(nV):
            for j in range(nV):
                G[i][j] = min(G[i][j], G[i][k] + G[k][j])
    return G

# The algorithm is similar to Floyd-Warshall
def floyd_warshall_rev(revenue, best_days_travel, city_to_start):

    nV = len(revenue)

    # Set G to array of zeroes by size of nV, When G[0] equals to the starting city revenue
    G = [revenue[0][city_to_start]] + [0]*(nV-1)

    # Set the start city as the best city we can go to in day zero
    StartCityArr = [city_to_start]
    best = city_to_start

    for day in range(1, nV): # For each day
        for city in range(len(revenue[0])): # For each city
            for Previous_Days in range(len(StartCityArr)): # For all previous days

                # The best way from the city we were in a few days ago to the current city
                travel_helper = best_days_travel[city][StartCityArr[Previous_Days]]

                # Normalize zero days travel time to one
                if travel_helper == 0: travel_helper = 1

                # Checks 2 things:
                # 1. Enough days have passed to get to this city
                # 2. The revenue of the current path is greater than the revenue of the best path so far

                if (day - travel_helper) >= Previous_Days and G[day] <= revenue[day][city] + G[Previous_Days]:

                    # The current path is the best one
                    G[day] = revenue[day][city] + G[Previous_Days]
                    # Update the last city visited on the best path
                    best = city

        # Append each day the last city visited on the best path to this day
        StartCityArr.append(best)

    return G


def main():
    #      city: a  b  c  # day:
    revenue = [[1, 2, 1],  # 0
               [3, 3, 1],  # 1
               [1, 1, 100]]  # 2

    #         city:  a   b   c    # city:
    days_travel = [[0, 1, 1],  # a
                   [1, 0, 1],  # b
                   [1, 2, 0]]  # c

    # Finds the best time to travel from each city to another
    best_days_travel = floyd_warshall_days(days_travel)

    # Finds the best travel by revenue from some "start city" for each number of day
    best_revenue_by_day = floyd_warshall_rev(revenue, best_days_travel,1)

    print(best_revenue_by_day)

main()

The code make use of dynamic programming, In each run of the outer loop the algorithm finds the optimal route for any city in a given number of days, which rises each run of the outer loop.

So in the first run the algorithm finds the best route from B under the condition that we have only one day

In the second run the algorithm finds the best route from B under the condition that we have only two days using the previous run

And so on...

So for the current data the output will look like this:

[2, 5, 102]

2 Is the answer for 1 day of job if starting from B

5 Is the answer for 2 days of job if starting from B

102 Is the answer for 3 days of job if starting from B

Answer 2

This problem seems simple to understand but complicated to code, at least for a rookie like me. I would approach this from the brute force method. In the example, we are only available for 3 days and travel days count for zero so that greatly reduces the brute of brute force. Let's have T represent travel days and A,B,C will be the cities. So then we have:

Day0 Day1 Day2  Expected 3-day Revenue
A     A    A       $  5
A     T    B          2 
A     T    C        101
B     B    B          6
B     T    A          3
B     T    C        102 
C     C    C        102
C     T    A          2
C     T    B          2

So, we just need to write code for each day linking day, city (or travel), and dollars and then compare the totals. Travel just creates $0 days. A piece of cake for some of you I'm sure. if I ever get to 50 points it will be a miracle.