動態規劃之

1/2ページ

動態規劃DP問題分類和經典題型

解題關鍵: 理解結構特徵,抽象出狀態,寫成狀態轉移方程。 動態規劃理念: 1.最優化原理    1951年美國數學家R.Bellman等人,根據一類多階段問題的特點,把多階段決策問題變換為一系列互相聯絡的單階段問題,然後逐個加以解決。一些靜態模型,只要人為地引進“時間”因素,分成 […]

【動態規劃·經典例題】雞蛋的硬度

雞蛋的硬度 總時間限制: 1000ms 記憶體限制: 65536kB 描述 最近XX公司舉辦了一個奇怪(super strange!)的比賽:雞蛋硬度之王爭霸賽。參賽者是來自世 界各地的母雞,比賽的內容是看誰下的蛋最硬,更奇怪的是XX公司並不使用什麼精密儀器來測量蛋的硬度,他們採用了一種最老土的辦法 […]

動態規劃–100層樓2只雞蛋最少次可以測試最高樓層不摔破

100層樓2個雞蛋 原題目:100層樓2個雞蛋最少需要幾次測試,才能得到摔破雞蛋的樓層; 轉換題目:兩個雞蛋,進行k次測試,最多可以測試多少層? 分析:第1個雞蛋測試所在的樓層高度為k層。 ①如果第1個雞蛋在第k層摔破了,第二個雞蛋就可以從第1層開始慢慢測試,最多k次可以測試到準確樓層; ②如果第1 […]

動態規劃與數學方程法解決樓層扔雞蛋問題

1.問題描述 兩個軟硬程度一樣的雞蛋,它們有可能都在一樓就摔碎,也可能從一百層樓摔下來沒事。有座100層的建築,用這兩個雞蛋確定哪一層是雞蛋可以安全落下的最高位置,可以摔碎兩個雞蛋,求給出一個最佳策略,測出雞蛋恰好不會碎的樓層,最佳策略滿足的條件就是在最壞情況下所扔的次數比其它任意策略的最壞情況下所 […]

【動態規劃】01揹包問題

01揹包問題 問題描述 給定 N 種物品和一個最大載重量為 C 的揹包,物品 i 的重量是 wi,其價值為 vi 。 問:應該如何選擇裝入揹包的物品,使得裝入揹包中的物品的總價值最大? 問題分析 對於每個物品,只能選擇裝或者不裝,不能選擇只裝物體的一部分,因此不能使用單位重量的價值進行排序的方法(貪 […]

動態規劃之單調佇列優化專題【附題目練習清單】

什麼是單調(雙端)佇列 單調佇列,顧名思義,就是一個元素單調的佇列,那麼就能保證隊首的元素是最小(最大)的,從而滿足動態規劃的最優性問題的需求。 單調佇列,又名雙端佇列。雙端佇列,就是說它不同於一般的佇列只能在隊首刪除、隊尾插入,它能夠在隊首、隊尾同時進行刪除。 【單調佇列的性質】 一般,在動態規劃 […]

動態規劃 (Dynamic Programming) 之 矩陣鏈乘法(Matrix Chain Multiplication)

這個問題是動態規劃的基礎的問題,也是演算法導論中討論過的問題。在這裡先簡單描述一下。假定有一組矩陣需要做乘法操作。但是我們知道首先矩陣乘法滿足了結合律。所以可以按照不同的順序做乘法。而且不同順序做乘法最後的乘法次數是不同的。比如〈A1, A2, A3〉分別是10 × 100, 100 × 5, 和 […]

動態規劃 (Dynamic Programming) 之 揹包問題合輯 (Knapsack, Subset Sum, Partition and change making problem )

揹包問題一直是動態規劃中的經典問題。這個問題又分成01揹包,完全揹包,多重揹包,分組揹包等等。。我在這裡只記錄下01揹包(0-1knapsack)和完全揹包(unbounded knapsack)。揹包問題的簡單描述就是有一個揹包和一堆物品。每個物品有自己的大小和價值。我們希望在一個特定容量的揹包中 […]