考慮以下問題:如何在DP表中實現這個遞歸算法?
我們有一艘長度爲L
的渡輪。這條渡輪用於在兩條河岸之間運輸車輛。渡輪有兩條車道,可以容納車輛。每輛車的長度爲l_i
。每條車道上的車輛可以容納,使得它們不超過渡輪的長度。給定一列長度爲l_1, l_2, ..., l_n
的車輛和長度爲L
的渡輪,找出可容納的最大車輛數量。
請記住,車輛只能根據他們在隊列中的位置進入渡輪。例如,如果隊列中的車輛長度爲700, 600
,且前方車輛較大,車道中剩餘的車位爲0, 400
,則不能裝載較短的車輛而不是較長的車輛。
我能夠使用遞推關係來解決這個問題。讓solve(L1, L2, l_i, l_i+1, ..., l_n)
返回長度爲l_i, l_i+1, ..., l_n
的車輛的最大數量,該車輛可以容納在其兩條車道中的長度爲L1, L2
的渡輪中。
function solve(L1, L2, l_i, l_i+1, ..., l_n) {
if (L1 - l_i > 0 and L2 - l_i > 0) {
return 1 + max(solve(L1 - l_i, L2, l_i+1, ..., l_n), solve(L1, L2 - l_i, l_i+1, ..., l_n))
} else if (L1 - l_i > 0) {
return 1 + solve(L1 - l_i, L2, l_i+1, ..., l_n)
} else if (L2 - l_i > 0) {
return 1 + solve(L1, L2 - l_i, l_i+1, ..., l_n)
} else {
return 0
}
}
基本上這個算法計算放置車輛在渡口並在每個復發的最佳方式,它減去當前車輛的長度在隊列中從兩個通道的長度和通過這本身並計算兩種策略的最大值。如你所見,遞歸調用建立得相當快,程序效率不高。我如何使用動態編程方式實現相同的算法?
編輯:約束條件是,L是1,10,000和之間的每個轎廂的長度爲100和3000之間
好的。因此,如果渡輪的長度是5000英尺,而轎廂的長度是2500,3000,1000,1000,1500,700,800,則該程序將生成一個5000 * 5000 * 7 3d陣列並計算其值。我對嗎?這將會非常低效,因爲我們將計算大量不需要的情況。有什麼方法可以減小數組的大小嗎? – Gerard
@Gerard你應該在我的朋友的第一位提供這個約束。從未看到他們在你的post.Give DP解決方案不知道它的約束從來就不是一個好主意:) –
@Gerard如果數組長度很小,你甚至可以考慮位掩模技術(在你的情況7),最好的事情在這裏提供了問題的鏈接:) –