Here is an O(n) approach without any advanced data structures.
dp[i] = max{dp[j] : m[i]-m[j] >= n} + a[i]
With the increasing of i, the optimal value in the brace will
not be descending. We can keep the optimal value so far and check if
there is a larger one.
#include <iostream>
using namespace std;
int profit(int m[], int p[], int n)
{
int i,j,dp[7] = {0},k,mx = 0;
for(j = 0, i=0;i<7;i++)
{
for (; j < i && m[i]-m[j] >= n; j++)
if (dp[j] > mx)
mx = dp[j];
dp[i] = mx+p[i];
}
for(i=0;i<7;i++)
cout<<dp[i]<<endl;
for(i=0;i<7;i++)
if(mx<dp[i])
mx = dp[i];
return mx;
}
int main()
{
int m[7] = {1,3,5,8,9,12,15};
int p[7] = {5,9,1,6,2,8,3};
cout<<"\nThe maximun profit is : "<<profit(m,p,5); //
}
On Jan 5, 3:06 am, Decipher <ankurseth...@gmail.com> wrote:
> Yuckdonald's is considering opening a series of restaurants along
> Quaint Valley Highway (QVH).The 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's may open at most one restaurant.The
> expected profi t from opening a restaurant at location i is pi, where
> pi > 0 and i = 1; 2; : : : ; n.
> 2)Any two restaurants should be at least k miles apart, where k is a
> positive integer.
> Give an effi cient algorithm to compute the maximum expected total
> pro fit subject to the given
> constraints.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
