2015-06-07 78 views
0

我試圖找到一個遞推關係和算法以下問題,但一直停留幾天:動態編程實踐算法

總共有H的>ñ小時在其中工作在n學校項目(所有這些項目都在同一時間到期),並且您現在想要決定現在分開這個時間。爲簡單起見,假設H是一個正整數,並且您將在每個項目上花費整數小時。你已經拿出了一套功能˚F ,...,˚Fñ(粗略估計,當然),使得在項目工作X小時我將讓你的等級f ix)。

可以假設˚FX)不會降低,如果X增加並且每個項目將在從1分被分級到100

因此,鑑於ħ˚F ,...,˚Fñ,你需要確定有多少(整數)小時,你將花費在每個幻燈ct所以你的平均等級越高越好(最高等級)。

  • 查找遞推關係爲ģ [ħĴ],其中ģ [ħĴ〕是用花ħ小時獲得的等級的總和關於課程1,2,...的項目總數j
  • 查找計算的動態規劃算法G [^hñ]

沒有人有想法?

+0

這只是[unbounded揹包問題](http://en.wikipedia.org/wiki/Knapsack_problem#Unbounded_knapsack_problem)的變相。 – Th3Cuber

回答

1

,我認爲這會工作:

G[H<0, j] = -Infinity 
G[H, 0] = 0 
G[H, j] = max(G[H-i, j-1]+f_j(i)) for 0<=i<=H 

在復發,我試圖找到的小時數最好對項目Ĵ工作。這個解決方案是O(H^2 * n)。