Dynamic Programming, max subarray with constraint

Question

So Ive been working on this problem which has to do with choosing a maximal sub array with a given constraint. The problem is as follows:

Yuckdonalds is considering opening a series of restaurants along Quaint Valley Highway (QVH). The 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, m1; m2; : : : ; mn

The constraints are as follows: At each location, Yuckdonalds may open at most one restaurant. The expected profit from opening a restaurant at location i is pi, where pi > 0 and i = 1;2; : : : ; n

Any two restaurants should be at least k miles apart, where k is a positive integer.

I have treated the sorted array M as a binary heap, and my algorithm consists of iterating through the binary heap for each index (in array M) and picking the max of its left/right child as long as it satisfies the distance constraint k. And then recursively calling the function with the index's left and right children.

It seems I am selecting a few optimal indices, as this is what th output suggests but I am missing something but I cant quite figure out what. PS. this is not for school, it was over a month ago and I am coding it for fun now, and I know my tempProfit variable is useless as of now

def binHandle(parent, M, P, tmp, lc):

    lastchosen = lc
    i = parent
    left = 2*i
    right = 2*i + 1
    if left > len(M):
            return

    parent = M[parent]

    if right <= len(M) and left < len(M):
            childRestL = M[left]
            childRestR = M[right]

            #choose best child
            if distance(lastchosen, childRestL) >= k:
                    if P[right] > P[left]:
                            outcome = P[right]
                            lastchosen = M[right]
                            tmp += outcome
                            print outcome
                            binHandle(right , M, P, tmp, lastchosen)

                    else:
                            outcome = P[left]
                            lastchosen = M[left]
                            tmp += outcome
                            print outcome
                            binHandle(left , M, P, tmp, lastchosen)

def maxprofits(M, P, k):
    maxProf = 0
    global tempProfit
    tempProfit = 0
    n = 1

    #test each index in array
    for n in range(1, len(M)):
            binHandle(n, M, P, tempProfit, 0)
            if tempProfit > maxProf:
                    maxProf = tempProfit
            tempProfit = 0
    return maxProf

edit: got it figured out

Why the downvote, the question is well written and effort is shown ?! ... — Rerito
– Rerito, Commented Nov 13, 2014 at 8:14

Rerito · Accepted Answer · 2014-11-13 08:20:56Z

1

The basic recursion is the following : you have your collection of candidates. You take the decision of whether or not you take the first restaurant. If you do so, you must get rid of the next candidates that are too close from it (distance < k). If you don't, you just get rid of the first location and proceed. In any case, you keep on examining wether or not you take the first location of the remaining set and so on.

In the end, you got the best result. Now, your question states dynamic programming ... That's a good thought, as we are going to use it to better the previous algorithm. Instead of starting from the full array, we will start from the end of it and store intermediate computation, here is how it works :

INPUTS : M[0..n-1], P[0..n-1], M is sorted in increasing order, P is such that P[i] is the profit related to the location M[i]

Let S[0..n-1] be an array of numeric values. We set S[i] = 0 for any i, except n-1, where S[n-1] = P[n-1], then we set an integer i to n-1. Let R[0..n-1] be an array of lists. For any i, R[i] = {}, except for n-1, R[n-1] = {n-1}
While i >= 0
1. Find j such that j = min(q ∈ [|i+1, n-1|], M[q] - M[i] > k). In other words, we find the minimal index that satisfies the distance criterion (after the current position).
  Note : To do that, you can run a binary search on M[i+1..n-1] to find M[i] + k. Just "tweak" the search process to return the first occurrence that is strictly superior instead of the result.
2. S[i] = max(P[i] + S[q], S[i+1]) (If q does not exist, then consider S[q] = 0 in the previous equation)
3. Depending on which is the optimal solution, R[i] <- {i} + R[q] or R[i] <- R[i+1]
S[0] is now the best profit you can have. R[0] is the list of the selected locations that provides this optimal result.

edited Nov 13, 2014 at 8:20

answered Nov 13, 2014 at 8:12

Rerito

6,11627 silver badges50 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Dhruvil Amin Over a year ago

Can we break down to weighted scheduling problem?

beroal Over a year ago

I believe that S[q] should be S[j].

Collectives™ on Stack Overflow

Dynamic Programming, max subarray with constraint

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related