問答題

【簡答題】一個旅行者要駕車從A地到B地,A、B兩地間距離為s。A、B兩地之間有n個加油站,已知第i個加油站離起點A的距離為di公里,0=d1n≤s,車加滿油后可行駛m公里,出發(fā)之前汽車油箱為空。應(yīng)如何加油使得從A地到B地沿途加油次數(shù)最少?給出用貪心法求解該最優(yōu)化問題的貪心選擇策略,寫出求該最優(yōu)化問題的最優(yōu)值和最優(yōu)解的貪心算法,并分析算法的時間復(fù)雜性。

答案: 貪心選擇策略:從起點的加油站起每次加滿油后不加油行駛盡可能遠,直至油箱中的油耗盡前所能到達的最遠的油站為止,在該油站再加...
微信掃碼免費搜題