Please provide a coded solution in python. Yuck Donald\'s is considering opening

Question

Please provide a coded solution in python.

Yuck Donald's is considering opening a series of restaurants along Quaint Valley Highway (QVH). The n possible locations are along a straight line, and the distances of these locations from the start of QVH are, in miles and in increasing order, m_1, m_2, ..., m_n. The constraints are as follows: At each location, Yuck Donald's may open at most one restaurant. The expected profit from opening a restaurant at location i is p_i, where P_i > 0 and i = 1, 2, ..., n. Any two restaurants should be at least k miles apart, where k is a positive integer. (The restaurants can also be at the distance of A: miles from each other.) Compute the maximum total profit subject to the given constraints. Input The input will have three lines. In each line, we will have space separated numbers. The first line of the input contains n and k -- the number locations and the lower bound on the distance (in miles) between consecutive restaurants. The second line contains then locations m_1, ..., m_n. The third line contains the vector of n profits p_1, ..., p_n. The inputs satisfy the following constraints: 0 lessthanorequalto n lessthanorequalto 20000, 0

Explanation / Answer

n = raw_input()
n = n.split()
m = int(n[1])
n = int(n[0])
l = raw_input()
l = l.split()
dis = []
for a in l:
   dis.append(int(a))
l = raw_input()
l = l.split()
profit = []
for a in l:
   profit.append(int(a))
cost = []
for j in range(0,n):
   tmp = []
   for i in range(0,n):
       tmp.append(0)
   cost.append(tmp)
for a in range(0,n):
   cost[a][a] = profit[a]
for size in range(1,n):
   for a in range(0,n-size):
       mx = profit[a]
       for k in range(a,a+size+1):
           tmp = profit[k]
           kk = -1
           for b in range(a,k):
               if(dis[k]-dis[b]<m):
                   break
               kk = b
           if(kk != -1):
               tmp+= cost[a][kk]
           kk = -1
           for b in range(a+size,k,-1):
               if(dis[b]-dis[k]<m):
                   break
               kk = b
           if(kk != -1):
               tmp+= cost[kk][a+size]
           if(tmp>mx):
               mx = tmp
       cost[a][a+size] = mx
#print(profit)
#print(cost)
print(cost[0][n-1])

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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