奧運指示牌的放置問題:海淀區某廣告公司負責為到京觀看奧運比賽的群眾設置指示
牌,他們的具體任務是從北京西客站到北科大奧運場館,沿途設置多個指示牌。假設北
京西客站到北科大奧運場館沿途有D 公里。指示牌放置的可能地點用數字x1,x2,…,
xn 給出,因此每個xi 處在區間[0,D]中。當然,指示牌上除了位置信息之外,還有廣告
信息,假設放一塊指示牌在地點xi,廣告公司會得到ri>0 的收益。
不過,指示牌不能任意放置,按照奧組委和北京市政管理部門的規定,兩塊指示牌之間
的相對距離必須大于5 公里。假設你作為該廣告公司的CTO,請設計一個算法來尋找
一組地點來放置指示牌,使得公司的廣告總收益在上述約束條件下達到最大。
標簽:
海
上傳時間:
2013-12-20
上傳用戶:chenlong