算法合集之動態(tài)規(guī)劃算法時間效率的優(yōu)化-文庫吧資料
2024-10-22 20:30本頁面
【正文】 j]=(a, b)， 0≤i≤n， 0≤j≤i， 0≤a≤m， 0≤b≤t， 表示在前 i首歌曲中選取 j首錄制所需的最少唱片為： a張唱片另加 b分鐘 。 問題的最優(yōu)解為： g[n,m,0]。 設 n首歌曲按照創(chuàng)作順序排序后的長度為 long[1..n]， 則動態(tài)規(guī)劃的狀態(tài)表示描述為： g[i, j, k]， (0≤i≤n， 0≤j≤m， 0≤kt), 表示前 i首歌曲 ， 用 j張唱片另加 k分鐘來錄制 ， 最多可以錄制的歌曲數(shù)目 。 輸入 n， m， t， 和 n首歌曲的長度 ， 它們按照創(chuàng)作順序排序 ，沒有一首歌超出一張唱片的長度 ， 而且不可能將所有歌曲的放在唱片中 。動態(tài)規(guī)劃算法時間效率的優(yōu)化 福州第三中學 動態(tài)規(guī)劃算法的時間復雜度 = 狀態(tài)總數(shù) *每個狀態(tài)轉移的狀態(tài)數(shù) *每次狀態(tài)轉移的時間 一、減少狀態(tài)總數(shù) 二、減少每個狀態(tài)轉移的狀態(tài)數(shù) 三、減少狀態(tài)轉移的時間 改進狀態(tài)表示； （例一） 減少決策時間 （例三） 方法：采用恰當?shù)臄?shù)據(jù)結構； 減少計算遞推式的時間 方法：進行預處理，利用計算結果等； 其他方法：選取恰當?shù)囊?guī)劃方向等； 根據(jù)最優(yōu)解的性質減少決策量； （例二） 其他方法：利用四邊形不等式證明決策的單調性等； 例一 、 Raucous Rockers 演唱組 （ USACO`96） [問題描述 ] 現(xiàn)有 n首由 Raucous Rockers 演唱組錄制的歌曲 ， 計劃從中選擇一些歌曲來發(fā)行 m張唱片 ， 每張唱片至多包含 t分鐘的音
教學課件相關推薦
鄂ICP備17016276號-1