#43508: 動態規劃五步法
chiuliyou@gmail.com
(邱立宇)
學校
:
新北市立永平高級中學
編號 : 136609
來源 : [106.1.117.161]
最後登入時間 ：
2024-10-26 13:36:59
動態規劃五步法
1. 構造問題: 在重量限制下找出最佳的價值組合
2. 定義狀態: f(i, j) = 前 i 個物品, 重量 j 的最高價值
3. 求解小規模的簡單問題:
f(0, j) = 0
f(i, 0) = 0
4. 狀態轉移方程式:
f(i, j) =
{
不選擇: f(i - 1, j)
選擇: f(i - 1, j - weight[i - 1]) + value[i - 1]
}
5. 判斷複雜度: O(n * mx)
因為每次都只需要前一行的資訊, 而自己就可以扮演前一行, 所以能夠壓縮到一維。
沒有壓縮記憶體會爆炸
沒有壓縮記憶體會爆炸
1. 構造問題: 在重量限制下找出最佳的價值組合
2. 定義狀態: dp[j] = 重量 j 的最高價值
3. 求解小規模的簡單問題:
dp[0] = 0
4. 狀態轉移方程式:
每一輪都加入新的貨物, 更新一遍
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
5. 判斷複雜度: O(n * mx)
ZeroJudge Forum