java - 使用动态编程的餐厅最大利润

它是一项任务，我花了2天的时间提出解决方案，但仍然有很多困惑，但是在这里我需要指出几点。问题如下:

Yuckdonald的餐厅正在考虑在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，但是如果我排除(餐馆25在利润13处)并包括(餐馆28在19利润19)，我最多可以有94 ...

如果我错了，请指出我，或者如果我错了，我该如何实现呢？

最佳答案

我能够发现2个错误:

您使用动态编程实际上不是，而是

，您只是将结果存储在一个数据结构中，如果程序按照您编写的方式工作并且仅执行了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

这里L[i] - L[i-1] < k对所有i都是正确的，因此结果将只是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)));
}