这是一个任务,我花了两天时间想出了解决方案,但仍有许多困惑,但在这里我需要澄清一些要点。以下是问题:
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分……
如果我错了,请指出来,或者告诉我如何实现它。