使用动态规划算法实现餐厅最大利润

Question

这是一个任务，我花了两天时间想出了解决方案，但仍有许多困惑，但在这里我需要澄清一些要点。以下是问题：

Yuckdonald’s正在考虑沿着QVH开设一系列餐厅。n个位置沿直线排列，并且这些位置与QVH起点的距离以英里为单位递增 m1, m2, ...., mn。约束条件如下：
1. 在每个位置，Yuckdonald可以开一家餐厅，预期从第i个位置开设餐厅的利润为pi
2. 任何两个餐厅之间应至少相隔k英里，其中k是一个正整数

我的解决方案：

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);

    }

}

这个解决方案给我88分，但是如果我排除（利润为13的25号餐厅）并包括（利润为19的28号餐厅），最多可以得到94分……

如果我错了，请指出来，或者告诉我如何实现它。

- SSH

---

你的问题是什么？你的代码输出结果不正确吗？ - user3437460

实际上，我认为我的逻辑不正确，所以在这里发布代码和对问题的理解，以便从专家那里获得一些反馈。 - SSH

我并没有给你点踩，但是你的帖子很可能会被这里的用户关闭，因为这个问题似乎更适合放在代码审查中。顺便问一下，你的代码是否给出了正确的输出？ - user3437460

下投票是为了什么？我不是在问解决方案，只是想知道缺失的东西或者我认为正确答案应该是94。 - SSH

我认为这不应该被踩。我也认为这不属于CR，因为用户认为（我没有验证）他没有正确的答案。 - Jean-François Savard

我认为递归是不正确的；“compute”的确切语义是什么？此外，动态规划通常不需要显式递归。 - Codor

Answer 1

我发现了两个错误：

你实际上没有使用动态规划

你只是将结果存储在数据结构中，这对于性能来说可能并不那么糟糕，如果程序按照你编写的方式运行，且只进行了1次递归调用。

然而，你至少进行了2次递归调用。因此，程序的运行时间为Ω(2^n)，而不是O(n)。

动态规划通常像这样工作（伪代码）：

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

你可以通过将数组元素初始化为-1（或者如果所有利润都是正数，则初始化为0）来实现这一点：

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];
    }
    ...

你认为之前的餐厅只能建在之前的位置。

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

相反，你应该使用最后一个距离至少为k英里的位置的利润。

示例

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

这里对于所有的 i 都成立 L[i] - L[i-1] < k，因此结果将只是 P[99] = 5，但实际上应该是 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)));
}

- fabian

Answer 2

据我的理解，这个问题可以用二维状态空间来建模，但我没有在提供的实现中找到。对于每一个(i,j) in{0,...,n-1}times{0,...,n-1}，让...

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)

请注意递归关系

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

其中lastpos(i)是距离起始位置最远的位置，但不能比位置i靠近k；第一种情况对应将位置i选择进解决方案，而第二种情况则对应省略位置j。整体解决方案可以通过计算profit(n-1,n-1)来获得；可以通过递归地进行评估，也可以通过自底向上地填充二维数组并在(n-1,n-1)处返回其内容来完成评估。

- Codor