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)
Answers:
Thank you for visiting the Q&A section on Magenaut. Please note that all the answers may not help you solve the issue immediately. So please treat them as advisements. If you found the post helpful (or not), leave a comment & I’ll get back to you as soon as possible.
Method 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
Method 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.
All methods was sourced from stackoverflow.com or stackexchange.com, is licensed under cc by-sa 2.5, cc by-sa 3.0 and cc by-sa 4.0