/**
动态规划(Dynamic Programming)技术广泛应用于许多组合优化问题中
e.g.
1.Floyd
2.矩阵链的乘法
3.最大效益投资
4.背包问题
5.最长公共子序列问题
6.图像压缩
7.最大子段和
8.最优二分检索树
9.RNA的最有二级结构
关键词：
记忆花搜索
01背包问题
*/
///01背包问题 的 深搜穷竭 #include "cstdio" #include "algorithm" #define N 105 int n=4,weight=5; int w[N]={2,1,3,2},v[N]={3,2,4,2}; int rec(int i,int j) { int res; if(i==n) { res=0; } else if(j<w[i])///不能放 { res=rec(i+1,j); } else { res=std::max(rec(i+1,j),rec(i+1,j-w[i])+v[i]);///放/不放 } return res; } int main() { printf("%d ",rec(0,weight)); }
/**
搜索深度为n，每层搜索都需要2层分支，Perfect Tree结构，最坏需要O(2^n)
等比级数复杂度，n较大时，不可取
*/
用数组记忆下重复计算的部分，优化为O(nW)
#include "cstdio" #include "cstring" #include "algorithm" #define N 105 int n=4,weight=5; int w[N]={2,1,3,2},v[N]={3,2,4,2}; int dp[N+1][N+1]; int rec(int i,int j) { if(dp[i][j]>=0) { return dp[i][j]; } int res; if(i==n) { res=0; } else if(j<w[i]) { res=rec(i+1,j); } else { res=std::max(rec(i+1,j),rec(i+1,j-w[i])+v[i]); } return dp[i][j]=res; } int main() { memset(dp,-1,sizeof(dp)); printf("%d ",rec(0,weight)); }
迭代式（递推式）
#include "cstdio" #include "cstring" #include "algorithm" #define N 105 int n=4,weight=5; int w[N]={2,1,3,2},v[N]={3,2,4,2}; int dp[N+1][N+1]; void solve() { for(int i=n-1;i>=0;i--) { for(int j=0;j<=weight;j++) { if(j<w[i]) { dp[i][j]=dp[i+1][j]; } else { dp[i][j]=std::max(dp[i+1][j],dp[i+1][j-w[i]]+v[i]); } } } } int main() { memset(dp,0,sizeof(dp)); solve(); printf("%d",dp[0][weight]); }
i的循环正序
for(int i=0;i<=n-1;i++) { for(int j=0;j<=weight;j++) { if(j<w[i]) { dp[i+1][j]=dp[i][j]; } else { dp[i+1][j]=std::max(dp[i][j],dp[i][j-w[i]]+v[i]);///你还剩多少重量 } } }
状态转移式 （前i个物品中选取总重不超过j）
for(int i=0;i<=n-1;i++) { for(int j=0;j<=weight;j++) { dp[i+1][j]=std::max(dp[i+1][j],dp[i][j]); if(j+w[i]<=weight) { dp[i+1][j+w[i]]=std::max(dp[i+1][j+w[i]],dp[i][j]+v[i]);///你已经放了多少重量 } } }
同一问题可能有各种各样的解决方法
对此题综上：
1.搜索的记忆化(计算过的就记住)
2.递推关系的DP（1.放不下 2.能放下（放与不放哪个合算？） 此状态来自上一行的哪一个容量 具体看书上的图）
3.从状态转移考虑的DP（此状态将转移到下一行的哪一个容量）
经典的LCS问题
#include "cstdio" #include "algorithm" #define N 1005 int n=4,m=4; char s[N]="abvd",t[N]="ddsd"; int dp[N+1][N+1]; void solve() { for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(s[i]==t[j]) { dp[i+1][j+1]=dp[i][j]+1;///找到一个相同的+1 } else { dp[i+1][j+1]=std::max(dp[i+1][j],dp[i][j+1]);///否则往前走 } } } printf("%d ",dp[n][m]); } int main() { solve(); }
完全背包问题
#include "cstdio" #include "cstring" #include "algorithm" #define N 105 int n=3,weight=7; int w[N]={3,4,2},v[N]={4,5,3}; int dp[N+1][N+1]; void solve() { for(int i=0;i<n;i++) { for(int j=0;j<=weight;j++) { for(int k=0;k*w[i]<=j;k++) { dp[i+1][j]=std::max(dp[i+1][j],dp[i][j-k*w[i]]+k*v[i]); ///此状态=此状态 还是 前状态+一堆？ } } } printf("%d ",dp[n][weight]); } int main() { memset(dp,0,sizeof(dp)); solve(); }
三重循环 O(nW^2)
减少多余计算，优化为 O(nW)
void solve() { for(int i=0;i<n;i++) { for(int j=0;j<=weight;j++) { if(j<w[i]) { dp[i+1][j]=dp[i][j]; } else { dp[i+1][j]=std::max(dp[i][j],dp[i+1][j-w[i]]+v[i]); } } } printf("%d ",dp[n][weight]); }
用一个数组实现
01背包
void solve() { for(int i=0;i<n;i++) { for(int j=weight;j>=w[i];j--) { dp[j]=std::max(dp[j],dp[j-w[i]]+v[i]); } } printf("%d ",dp[weight]); }
完全背包
void solve() { for(int i=0;i<n;i++) { for(int j=w[i];j<=weight;j++) { dp[j]=std::max(dp[j],dp[j-w[i]]+v[i]); } } printf("%d ",dp[weight]); }
上述写法 两者差异只有循环的方向
两个数组滚动时用，来实现重复利用
void solve() { for(int i=0;i<n;i++) { for(int j=0;j<=weight;j++) { if(j<w[i]) { dp[(i+1)&1][j]=dp[i&1][j]; } else { dp[(i+1)&1][j]=std::max(dp[i&1][j],dp[(i+1)&1][j-w[i]]+v[i]); } } } printf("%d ",dp[n&1][weight]); }
以前01背包，我们针对不同的重量，限制计算最大价值，复杂度O(nw)
而当W非常大时，我们需要采取另一种方法，针对不同的价值，计算最小的重量（依据算法的规模改变算法的情况是存在的）
P62
最长上升子序列问题(LIS Longest Increasing Subsequence)
#include "cstdio" #include "algorithm" #define N 1005 int n=5; int a[N]={4,2,3,1,5}; int dp[N];///dp[i]为以ai为末尾的最长子序列长度 void solve() { int res=0; for(int i=0;i<n;i++) { dp[i]=1; for(int j=0;j<i;j++)///往前找寻美妙的回忆 { if(a[j]<a[i]) { dp[i]=std::max(dp[i],dp[j]+1); } } res=std::max(res,dp[i]); } printf("%d ",res); } int main() { solve(); return 0; }
O(n^2)
#include "cstdio" #include "algorithm" #define N 1005 #define INF 0X3f3f3f3f using namespace std; int n=5; int a[N]={4,2,3,1,5}; int dp[N];///dp[i]=长度为i+1上升子序列中末尾元素的最小值 void solve() { std::fill(dp,dp+n,INF); for(int i=0;i<n;i++) { *lower_bound(dp,dp+n,a[i])=a[i];///二分查找>=a[i]的最小位置，返回指针 } printf("%d ",lower_bound(dp,dp+n,INF)-dp); } int main() { solve(); }
O(nlogn)