Restaurant Maximum Profit using Dynamic Programming

Question

Its an assignment task,I have spend 2 days to come up with a solution but still having lots of confusion,however here I need to make few points clear. Following is the problem:

Yuckdonald’s is considering opening a series of restaurant along QVH. 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 m1, m2, ...., mn. The constraints are as follows:
1. At each location, Yuckdonald may open one restaurant and expected profit from opening a restaurant at location i is given as pi
2. Any two restaurants should be at least k miles apart, where k is a positive integer

My solution:

public class RestaurantProblem {

    int[] Profit;
    int[] P;
    int[] L;
    int k;



    public RestaurantProblem(int[] L , int[] P, int k) {
        this.L = L;
        this.P = P;
        this.k = k;
        Profit = new int[L.length];
    }



    public int compute(int i){
        if(i==0)
            return 0;


        Profit[i]= P[i]+(L[i]-L[i-1]< k ? 0:compute(i-1));//if condition satisfies then adding previous otherwise zero
        if (Profit[i]<compute(i-1)){
                Profit[i] = compute(i-1);
            }
        return Profit[i];
    }

    public static void main(String args[]){
        int[] m = {0,5,10,15,19,25,28,29};
        int[] p = {0,10,4,61,21,13,19,15};
        int k = 5;

        RestaurantProblem rp = new RestaurantProblem(m, p ,k);
        rp.compute(m.length-1);
        for(int n : rp.Profit)
            System.out.println(n);

    }

}

This solution giving me 88 however if I exclude (Restaurant at 25 with Profit 13) and include (Restaurant 28 with profit 19) I can have 94 max...

point me if I am wrong or how can I achieve this if its true.

Answer 1

I was able to identify 2 mistakes:

You are not actually using dynamic programming

, you are just storing the results in a data structure, which wouldn't be that bad for performance if the program worked the way you have written it and if you did only 1 recursive call.

However you do at least 2 recursive calls. Therefore the program runs in Ω(2^n) instead of O(n).

Dynamic programming usually works like this (pseudocode):

calculate(input) {
     if (value already calculated for input)
          return previously calculated value
     else
         calculate and store value for input and return result
}

You could do this by initializing the array elements to -1 (or 0 if all profits are positive):

Profit = new int[L.length];
Arrays.fill(Profit, -1); // no need to do this, if you are using 0

public int compute(int i) {
    if (Profit[i] >= 0) { // modify the check, if you're using 0 for non-calculated values
        // reuse already calculated value
        return Profit[i];
    }
    ...

You assume the previous restaurant can only be build at the previous position

Profit[i] = P[i] + (L[i]-L[i-1]< k ? 0 : compute(i-1));
                                     ^
                  Just ignores all positions before i-1

Instead you should use the profit for the last position that is at least k miles away.

Example

k = 3
L   1   2   3   ...   100
P   5   5   5   ...     5

here L[i] - L[i-1] < k is true for all i and therefore the result will just be P[99] = 5 but it should be 34 * 5 = 170.

---

int[] lastPos;

public RestaurantProblem(int[] L, int[] P, int k) {
    this.L = L;
    this.P = P;
    this.k = k;
    Profit = new int[L.length];
    lastPos = new int[L.length];
    Arrays.fill(lastPos, -2);
    Arrays.fill(Profit, -1);
}

public int computeLastPos(int i) {
    if (i < 0) {
        return -1;
    }
    if (lastPos[i] >= -1) {
        return lastPos[i];
    }
    int max = L[i] - k;
    int lastLastPos = computeLastPos(i - 1), temp;
    while ((temp = lastLastPos + 1) < i && L[temp] <= max) {
        lastLastPos++;
    }
    return lastPos[i] = lastLastPos;
}

public int compute(int i) {
    if (i < 0) {
        // no restaurants can be build before pos 0
        return 0;
    }
    if (Profit[i] >= 0) { // modify the check, if you're using 0 for non-calculated values
        // reuse already calculated value
        return Profit[i];
    }

    int profitNoRestaurant = compute(i - 1);
    if (P[i] <= 0) {
        // no profit can be gained by building this restaurant
        return Profit[i] = profitNoRestaurant;
    }

    return Profit[i] = Math.max(profitNoRestaurant, P[i] + compute(computeLastPos(i)));
}

Answer 2

To my understanding, the prolem can be modelled with a two-dimensional state space, which I don't find in the presented implementation. For each (i,j) in{0,...,n-1}times{0,...,n-1}` let

profit(i,j) := the maximum profit attainable for selecting locations
               from {0,...,i} where the farthest location selected is
               no further than at position j
               (or minus infinity if no such solution exist)

and note that the recurrence relation

profit(i,j) = min{ p[i] + profit(i-1,lastpos(i)),
                          profit(i-1,j)
                 }

where lastpos(i) is the location which is farthest from the start, but no closer than k to position i; the first case above corresponds to selection location i into the solution while the second case corresponds to omitting location j in the solution. The overall solution can be obtained by evaluating profit(n-1,n-1); the evaluation can be done either recursively or by filling a two-dimensional array in a bottom-up manner and returning its contents at (n-1,n-1).