noip教程動態(tài)規(guī)劃ppt課件-資料下載頁
2025-05-05 18:18本頁面
【正文】 化搜索來實現(xiàn) Part 3. 狀 態(tài)壓縮動態(tài)規(guī) 劃 ? 放寒假了，小 D終于可以回家了。一個學(xué)期之后他有太多的東西想帶回家。 小 D的背包可以被看作一個 4行 N列的矩陣，每個物品放入背包的物品恰好需要占據(jù)兩個相鄰的方格，任意兩個物品不能占據(jù)相同的方格。為了充分的利用自己的背包，小 D希望背包的所有空間都放置了物品，也就是說，背包中恰好放入了 2N個物品。 現(xiàn)在小 D想知道，不同的放置方案數(shù)有多少種。 例 9. 多米諾骨牌覆蓋 ? 搜索？ ? n很大，超時嚴(yán)重 ? 動態(tài)規(guī)劃？ ? 如何表示狀態(tài)？ ? 注意到每一列最多只有 4行，每一個格子對下一行的影響只有 2種：下一行對應(yīng)的格子是否可以和當(dāng)前格子一起放進(jìn)一個物品 ? 狀態(tài)壓縮！ 0/1表示每個格子的狀態(tài)， 4位二進(jìn)制數(shù)表示一行的狀態(tài) Solution ? 用 F[k][S]來描述一個狀態(tài)，這個狀態(tài)表示已經(jīng)把矩陣的前 k1列全部放滿，并且第 k列的覆蓋情況為 S（ s為一個 4位二進(jìn)制數(shù)），此時的擺放方案數(shù)（注意，其實只有 S中 1的個數(shù)為偶數(shù)時狀態(tài)才有意義，更加深入的探討會發(fā)現(xiàn)需要使用的狀態(tài)很少）。 ? 通過枚舉第 k列骨牌的放置方案，不難得到從 F[k][u]（ u = 0 ? 15 ）到 F[k+1][v]（ v = 0 ? 15 ）的轉(zhuǎn)移方程。這個過程需要另外寫一個程序去枚舉才能完成。 Solution ? L盞燈，每盞燈為 0/1，表示亮的或暗的 ? 有一個叉子有 T個叉尖，相鄰兩個叉尖的距離等于相鄰兩盞燈的距離。有些叉尖斷了，用 0表示，否則為1 ? 叉子對準(zhǔn)開關(guān)，可以改變燈的狀態(tài) ? 已知初始燈的狀態(tài)和叉尖狀態(tài)，求叉尖操作的序列使得最后亮著的燈最少 ? L=50, T=7 例 ? 同一位置只可能操作一次 ? 可以從左到右依次操作 ? F[i][S]表示最后 T盞燈燈的狀態(tài)為 S時，前 i盞燈至少還亮著多少盞 ? S為一個 T位二進(jìn)制， 0表示暗， 1表示亮 ? 枚舉是否在 iT+1~i+1操作，從而轉(zhuǎn)移到 F[i+1][K] ? 時間復(fù)雜度： O(L*2^T) Solution ? 一定要符合最優(yōu)化原理，即滿足最優(yōu)子結(jié)構(gòu) ? 可按照某一順序，從小到大求解 ? 從大到小求解可用記憶化搜索 ? 注意邊界條件 ? 轉(zhuǎn)移方程一定要清晰，不要漏情況 ? 狀態(tài)的意義一定要清晰 DP注意事項 Thx～ Questions are wele ?
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1