尋找動態算法來確定最優序列

這是班上給出的作業問題，我想知道我是否可以得到一些幫助。尋找動態算法來確定最優序列

問題是，有一個老頭。他在公園裏。該公園包括c_1, c_2, c_3, ....c_n長長的單人路線，其中c_1最接近老人，c_n是老人想要坐的最後一個長椅。

他理想上可以在沒有任何幫助的情況下行駛120英尺。但是，他的旅行時間超過120英尺，他會很容易疲倦，而且他旅行的次數會減少，坐在板凳上並起牀會有時間上的缺點。因此，對於每一次散步而言，步行的懲罰將爲(120-x)^4，其中x是他上次在替補席上休息後到目前爲止所走過的路程。

如果臺位於各120兩腳分開，這將讓他沒有懲罰，因爲他正好可以在每一個他遇到板凳休息，這會讓120英尺旅遊，和0點球。顯然，如果他認爲自己迄今還沒有走過120英尺，但只有10或20英尺，他可以跳過替補席。

的目標是找到一種算法使用具有良好的時間複雜度動態規劃，讓他在某種程度上最小的總損失。他在替補席上休息多少次並不重要，但要找到一個能夠給出最低總體罰分的替補名單。

你是否認爲這是可能實現比爲O（n^2）的時間複雜度？我認爲這與硬幣問題或美式足球得分問題非常相似，但其對兩個長凳之間的每一次旅行的'（120-x）^ 4'罰款讓我頭疼。

2012-02-21 user482594

我記得大約一年前的一個類似的問題，但我找不到它。 :( – biziclop 2012-02-21 20:33:44

我在「http：// stackoverflow」上發現了非常類似的問題。com/questions/4950956 /你會怎麼樣在開發一個算法爲這個酒店問題「，並幫助我很多 – user482594 2012-02-22 04:12:58

它已經一段時間，因爲我已經做了動態規劃什麼，但我會採取刺傷。

讓P[i]從板凳c_i開始的最低刑罰。

讓cost(i)成爲從長凳c_i開始並去到c_n的懲罰。對於i=n這將是0，否則它是(120-x)^4而x是長凳之間的距離。

for i = n to 1 
    P[i] = cost(i) 
    for j = i + 1 to n 
     P[i] = min(P[i], P[j])

我們從過去的板凳向後工作，並檢查走到最後板凳，步行到當前的替補和替補最後之間的任何替補之間的最低成本。

這運行在O（n^2）時間複雜度。

2012-02-21 20:40:43 Lester

是的，這是我迄今發現的，但是想知道我是否可以在O（n log n）時間使用記憶來做到這一點 – user482594 2012-02-21 20:53:07

我認爲在第二個循環中可以進行memoization的優化，通過自下而上的方式來建立懲罰，最後的替補並不需要計算所有可能的懲罰 – user482594 2012-02-22 03:35:20

另一個解決方案是構造一個圖形，每個椅子作爲節點。節點i和j（ij）如果它們之間的距離小於或等於120英尺。根據懲罰函數對每個邊進行加權。

現在找到開始和結束節點之間的最短距離。

如果圖是稀疏（即長椅稀疏地間隔開），則可以實現O（nlogn）邊緣的假設數目爲O（n）。

2012-02-21 23:25:03 ElKamina

如果工作臺不稀疏，則會有O（n^2）個邊緣？ – user482594 2012-02-22 02:44:04

回答