-
動態規劃：
-
原理：要滿足最優子結構和重疊子問題，使用遞回式自底向上計算并保存最優解，找到整體最優解
-
與貪心的一些區別：
- 滿足貪心一定滿足最優子結構，但滿足最優子結構不一定滿足貪心選擇性質，比如背包問題
-
基本模板
-
01背包
for(i=0; i<n; i++) { for(j=m; j>w[i]; j--) { //m -> max weight f[j] = max(f[j],f[j-w[i]]+v[i]); } } -
完全背包
for(i=0; i<n; i++) { for(j=w[i]; j<=m; j++) { f[j] = max(f[j],f[j-w[i]]+v[i]); } } -
多重背包
while(n--) { ret = s; //rest things k = 1; //2>>k while(rest >= k) { w[++cnt] = w0*k; c[cnt] = c0*k; rest = rest-k; k *= 2; } if(rest>0) { w[++cnt]=w0*rest; c[cnt]=c0*rest; } } for(i=1; i<=cnt; i++) { for(j=v; j>=w[i]; j--) { dp[j] = max(dp[j],dp[j-w[i]]+c[i]); } }
-
-
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/101261.html
標籤：其他
上一篇：演算法模板：貪心