备注:Day1 Day2记得笔记太233,所以就不发了
备注2:Day4~Day7发不发看心情qaq
(7.17持续更新中...)
动态规划A 记忆化搜索 & 动态规划初步
8点15: 杨姓dalao唠叨了几句;8点20:上课正式开始
part1 记忆化搜索
数字金字塔:luogu 1216
一、搜索(dfs)
没一个点向左或向右走
void dfs(int x,int y,int val)
{
val+=a[x][y];
if(x==n-1)
{
if(val>ans)ans=val;
return;
}
dfs(x+1,y,val);
dfs(x+1,y+1,val);
}
二、记忆化搜索:
冗余搜索:无用的,不会改变答案的搜索。
我们在search过程中可能会n次都走到某一个点,其中n-1次搜索即使继续搜索下去,答案也不会改变。
那么,怎么优化程序?对于每一个位置都记录一个值,代表搜到此位置时,最大路径和时多少
void dfs(int x, int y, int val)
{
val += a[x][y];
if(val <= f[x][y]) return;
f[x][y] = val;
if(x == n-1)
{
if(val > ans) ans = val;
return;
}
dfs(x+1, y, val);
dfs(x+1, y+1, val);
}
背包问题:luogu 1048
一、搜索:
状态(x,w,v)——搜到第x件物品,物品总质量w,总价格v
行动——我要不要
约束——物品总质量不超过最大值
目标——物品总价值最大
冗余:(x1,w1,v1)和(x2,w2,v2)时,x1=x2,w1=w2,v1<v2,那么前者冗余
二、记忆化搜索
void dfs(int t,int x,int val)
{
if(val<=f[t][x])return;
f[t][x]=val;
if(x==n)
{
if(val>ans)ans=val;
return;
}
dfs(t,x+1,val);
if(t>=w[x])dfs(t-w[x],x+1,val+v[x]);
}
其实,就是对于冗余的情况不再搜索......(这让我想起了滑雪)
part2.动态规划
在最优路径上走,每走一步都是最大值。
最优性:设走到某一个位置的时候,它达到了路径的最大值,
dp:只记录状态的最优值,并用最优值来推导其他的最优值。
记录f[i][j]路径最大值,有两种方法推导:
顺推;逆推。
数字金字塔:luogu 1216
顺推:f[i][j]->f[i+1][j]、f[i+1][j+1];
逆推:f[i-1][j];f[i-1][j-1]->f[i][j];
//顺推
f[0][0]=a[0][0];
for(int i=0;i<n-1;++i)
for(int j=0;j<=i;++j)
{
f[i+1][j]=max(f[i+1][j],f[i][j]+a[i+1][j]);
f[i+1][j+1]=max(f[i+1][j+1],f[i][j]+a[i+1][j+1]);
}
//逆推
f[0][0]=a[0][0];
for(int i=0;i<n;++i)
{
f[i][0]=f[i-1][0]+a[i][0];
f[i][i]=f[i-1][i-1]+a[i][i];
for(int j=1;j<i;++j)
f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j];
}
ans=0;
for(int i=0;i<n;++i)
ans=max(ans,f[n-1][i]);
状态转移方程
顺推:{fangcheng}
逆推:{fangcheng}
逆推改变搜索顺序
for(int i=0;i<n;++i)
f[n-1][i]=a[n-1][i];
for(int i=n-2;i>=0;--i)
for(int j=0;j<=i;++j)
f[i][j]=max(f[i+1][j+1],f[i+1][j])+a[i][j];
ans=f[0][0];
这种做法不需要判断边界了
顺推、逆推依个人喜好而定(反正我喜欢逆推??????)
转移顺序:最优值之间的推导顺序
能使用dp做的题:有明确的推导顺序。数字金字塔里就有——自上而下。
能分成不同的阶段,阶段逐步进行。和搜索顺序是类似的
划分好阶段,前往后、后往前推都ok
用一维数组写背包问题
背包 记录f[i][j]:决定前i件物品,在总重量j情况下,物品总价值最大值
状态转移方程:状态之间的推导公式
顺推:我这一个状态,下一步去哪里?
逆推:从什么状态可以到达我这里?
背包 顺推
for(int i=0;i<n;++i)
for(int j=0;j<=t;++j)
{
f[i+1][j]=max(f[i+1][j],f[i][j]);
if(j+w[i]<=t)
f[i+1][j+w[i]]=max(f[i+1][j+w[i]],f[i][j]+v[i]);
}
ans=0;
for(int i=0;i<=t;++i)ans=max(ans,f[n][i]);
背包 逆推
for(int i=1;i<=n;++i)
for(int j=0;j<=t;++j)
{
f[i][j]=f[i-1][j];
if(j>=w[i])f[i][j]=max(f[i][j],f[i-1][j-w[i]]+v[i]);
}
ans=0;
for(int i=0;i<=t;++i)ans=max(ans,f[n][i]);
数组压缩:
用一个一维数组代替二维数组
f[i]只由f[i-1]决定,其它的就没用了(优化空间复杂度)
只能倒着枚举了
代码实现
for(int i=1;i<=n;++i)
for(int j=t;j>=0;--j)
{
//不取:对数组没有影响
//f[i][j]=f[i-1][j];
//取
//if(j>=w[i])f[i][j]=max(f[i][j],f[i-1][j-w[i]]+v[i]);
if(j>=w[i])f[j]=max(f[j],f[j-w[i]]+v[i]);
}
不建议写一维数组,因为有害,空间不够写滚动数组
9点25 课间休息......
9点40 继续上课......
完全背包
poj 1384 http://poj.org/problem?id=1384
完全背包的数组压缩比较简单了for(i=1 to n) for(j=0 to m) if(j>=w[i])f[j]=min(f[j],f[j-w[i]]+p[i];
顺着枚举是完全背包,逆着01
多重背包不要用一维!能用二维干嘛要用一维。。。
背包计数问题:luogu1466 集合
把数字i看成质量i的物品,求出装满重M背包的方案数(然后除以2)
顺推
f[1][0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=m;++j)
{
f[i+1][j]+=f[i][j];
if(i+1<m)f[i+1][i+j]+=f[i][j];
}
逆推
f[0][0]=1;
for(i=1 to n)
for(j=0 to m)
{
f[i][j]=f[i-1][j];
if(j>=i)f[i][j]+=f[i-1][j-1];
}
数组压缩
g[0]=1;
for(i=1 to n)
for(j=m to i)
g[j] += g[j-i];
luogu 货币系统
10点20下课
10点30上课
多重背包:物品有数量限制
01:只有一件
完全:无数量限制
完全背包
多件物品:拆解成1件物品组成的物品+两件+四件......,单独出售,变成01背包
为什么怎么做呢?因为二进制的神奇功效
【下午做题】
一、洛谷P1004 方格取数
二、导弹拦截
三、合唱队形
四、LCS(LCS转为LIS,用nlog2n解决)
五、LCS洛谷有关例题
待更