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.
http://codepad.org/DDtJ6yBF
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.
http://codepad.org/DDtJ6yBF
No comments:
Post a Comment