算法動態程序

我今天正在愛爾蘭讀一本計算機科學雜誌，它有一個回答這個問題的競賽。任何人都可以幫助我解決它。算法動態程序

問題所在。

給定x1 ...，xn，確定EMP應該激活的次數銷燬外星人的最大數量。

例子。假設n = 4且x1 ... x4 = 1,10,10,1，那麼最好的解決方案是是在第三和第四分鐘激活EMP。在第3分鐘，它破壞了分鐘（10,3^2）= 9個外星人。然後在第4分鐘，它破壞了最小（1,1^2）= 1的外星人。這共有10個外國人。

2問題

（a）令S（j）的表示破壞對於由僅在第j個分鐘到達的外國人的子問題外國人的最大總數。對S（j）給出一個遞歸公式。另外，寫下基本情況。（提示：對於S（j），你總是在第j分鐘激活 EMP。假設之前的激活發生在第i分鐘。嘗試i的所有可能性並採取最大限度。）

（b）爲這個問題提供一個動態編程算法。分析算法的時間和空間複雜度。

要點： - 一羣外星人在n分鐘內到達。在第i分鐘，xi外國人到達。根據遙感數據，你可以預先知道這個序列x1 ... xn。

您可以隨時使用電磁脈衝（EMP），它可以摧毀外星人的某些。 EMP的能力取決於它允許多長時間收取。爲了做到這一點，如果自EMP上次使用以來j分鐘過去了，那麼能夠銷燬j2外星人。

EMP只會破壞到達激活的確切時間的外星人。換句話說，它不會摧毀任何早到或晚來的外星人。因此，如果它在第k分鐘被使用，並且它已經被使用了j分鐘，那麼它破壞了min（xk，j2）外星人（即，無論哪個xk或j2更小）。

每次使用後，EMP將完全耗盡。我們還假設EMP從第0分鐘開始關閉（）爲完全耗盡。

來源

2012-03-28 user1261083

機器人從哪裏來？你有什麼基礎要繼續下去，比如知道動態編程是什麼？ – birryree 2012-03-28 16:31:48

是的，我一直試圖在過去的3個小時裏瘋狂地學習它。我明白，它遞歸地使問題變小，直到達到基本情況，這些被保存以幫助節省內存並且不再解決同樣的問題兩次。 – user1261083 2012-03-28 16:34:32

如果我回答問題，我可以拿到禮品卡嗎？你有任何努力？ – Blender 2012-03-28 16:34:35

（a）這個提示真的給了它。顯然是S(0) = 0，而S(1) = 1。我們有：

S(j) = max{S(i) + min(x[j], (j - i)^2) : 0 <= i < j}。這真的只是做暗示說。下面是它如何在你的榜樣運行：

1 10 10 1 
S(0) = 0 
S(1) = 1 
S(2) = max{S(0) + min(x[2], (2-0)^2), S(1) + min(x[2], (2 - 1)^2)} = 
    = max{0 + 4, 1 + 1} 
    = 4 
S(3) = max{S(0) + min(x[3], (3 - 0)^2), S(1) + min(x[3], (3-1)^2), S(2) + min(x[3], (3-2)^2)} 
    = max{0 + 9, 1 + 4, 4 + 1} 
    = 9 
S(4) = max{S(0) + min(x[4], (4 - 0)^2), ..., S[3] + min(x[4], (4-3)^2)} 
    = max{0 + 1, ..., 9 + 1} 
    = 10

（B）我已經解決了上面。只需將S作爲一個數組。由於每個S(i)的計算需要迭代所有的j < i，因此每個S(i)需要O(n)時間，所以整個算法是O(n^2)。

來源

2012-03-28 17:35:57 IVlad

算法動態程序

回答

相關問題