- 搜標(biāo)題
- 搜題干
- 搜選項(xiàng)
問(wèn)答題
【簡(jiǎn)答題】一個(gè)旅行者要駕車(chē)從A地到B地，A、B兩地間距離為s。A、B兩地之間有n個(gè)加油站，已知第i個(gè)加油站離起點(diǎn)A的距離為di公里，0=d1
【簡(jiǎn)答題】一個(gè)旅行者要駕車(chē)從A地到B地，A、B兩地間距離為s。A、B兩地之間有n個(gè)加油站，已知第i個(gè)加油站離起點(diǎn)A的距離為di公里，0=d1n≤s，車(chē)加滿(mǎn)油后可行駛m公里，出發(fā)之前汽車(chē)油箱為空。應(yīng)如何加油使得從A地到B地沿途加油次數(shù)最少？給出用貪心法求解該最優(yōu)化問(wèn)題的貪心選擇策略，寫(xiě)出求該最優(yōu)化問(wèn)題的最優(yōu)值和最優(yōu)解的貪心算法，并分析算法的時(shí)間復(fù)雜性。
答案：
貪心選擇策略：從起點(diǎn)的加油站起每次加滿(mǎn)油后不加油行駛盡可能遠(yuǎn)，直至油箱中的油耗盡前所能到達(dá)的最遠(yuǎn)的油站為止，在該油站再加...
你可能感興趣的試題
問(wèn)答題
【簡(jiǎn)答題】
下面是用回溯法求解馬的周游問(wèn)題的算法；空白處應(yīng)填？
馬的周游問(wèn)題：給出一個(gè)n*n棋盤(pán)，已知一個(gè)中國(guó)象棋馬在棋盤(pán)上的某個(gè)起點(diǎn)位置（x0，y0），求一條訪問(wèn)每個(gè)棋盤(pán)格點(diǎn)恰好一次，最后回到起點(diǎn)的周游路線。（設(shè)馬走日字。）
算法HORSETRAVEL
輸入：正整數(shù)n，馬的起點(diǎn)位置x0，y0），1<=x0，y0<=n。
輸出：一條從起點(diǎn)始訪問(wèn)n*n棋盤(pán)每個(gè)格點(diǎn)恰好一次，最后回到起點(diǎn)的周游
路線；若問(wèn)題無(wú)解，則輸出nosolution。
答案：
（1）i>=1
（2）k[i]+1
（3）1
（4）i+1
（5）k[i]=0<...
（2）k[i]+1
（3）1
（4）i+1
（5）k[i]=0<...
