动态规划:
原理:要满足最优子结构和重叠子问题,使用递归式自底向上计算并保存最优解,找到整体最优解
与贪心的一些区别:
基本模板
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.cnblogs.com/syisyuan/p/13708462.html