简单动态规划

简单动态规划

0 说明

前备知识请看递推与记忆化搜索

1 基础

1.1 介绍

动态规划是运筹学的一个分支,是求解决策过程最优化的数学方法。动态规划不是算法,是一种思想。这种思想把大问题转化为小问题,用小问题的解推断出大问题的解

1.2 例子

  • 问题一:有$n$级台阶,一开始站在0级,每次可以向上走1级或2级,问走到n级的方案总数?

暴力的思想是从0级模拟一直到n级,每次都有两种选择,这种做法的复杂度是指数级的。

有没有一种更好的思想?创建一个数组$f$,以$f[n]$表示从0级到n级的方案数,如果$f[1],f[2],...,f[n-1]$都知道的话,怎么推出$f[n]$?

可以看出,走到当前台阶要么是前一个台阶,要么是前两个台阶,而前一个台阶或前两个台阶又是可以看作当前台阶,所以可以得到递推式:

$$ f[n]=f[n-1]+f[n-2](n \geq 3) $$

其中初始条件是$f[1]=1,f[2]=2$

  • 问题二:你手上有无限多的1,5,11元硬币,给定一个数字$n(n \geq 1)$,问凑出n元需要最少多少枚硬币?

最直接可能想到贪心,也就是每次都找能用的最大面额,但是在$n=15$时遇到了错误,如果是贪心,$11+1+1+1+1$一共是5枚,而$5+5+5$却只需要三枚,所以不能这么做。

我们可以类比问题一的思想:创建一个数组$f$,以$f[n]$表示凑出n元的最小方案数,如果$f[1],f[2],...,f[n-1]$都知道的话,怎么推出$f[n]$?

可以看出,本题有三个选择方案,所以,如果要求方案数最小,那么就选择这三个方案数里面最优的,用式子表达如下:

$$ f[n]=min\left\{\begin{matrix} 1+f[n-1]\\ 1+f[n-5]\\ 1+f[n-11] \end{matrix}\right. $$

其中初始条件是$f[0]=0$

1.3 状态

上面的两个问题我们用了“把大问题转化为小问题,用小问题的解推断出大问题的解”的思想来做,为什么可以这样做呢?这是因为大问题和小问题都有一样的形式

  • 问题一

    • 大问题:走到n级有多少种方案
    • 小问题:走到n-1级有多少种方案,走到n-2级有多少方案
    • 它们都是“走到[...]级有多种方案”
  • 问题二

    • 大问题:凑出n元硬币的最小方案数
    • 小问题:凑出n-1元硬币的最小方案数,凑出n-5元硬币的最小方案数,凑出n-11元硬币的最小方案数
    • 它们都是“凑出[...]元硬币的方案数”

只有大问题和小问题拥有相同的形式,才可以用动态规划这种思想。题目如果满足这个要求,我们遇到每个问题都可以很简洁的表达,这些可能遇到的“局面”称之为状态

设计完状态后,只要能利用小状态的解求出大状态的解,就可以求解题目。

1.4 LIS问题

数组的最长上升子序列是指最长的那一个单调上升的子序列。例如一个数组[1,3,7,4,6,9],它的最长上升子序列是[1,3,4,6,9]。

如果要用动态规划的思想来做,需要先设计状态。如何设计状态?(设数组为a,求解数组为f)

  • 状态:以$a[x]$为结尾的上升子序列最长有多长

用$f[x]$来表示状态的解,那么答案就是$f[1]$到$f[n]$中最大的一个。可以很明显看出,最长的上升子序列一定是插在某个上升子序列的尾部得到的。

考虑上面给出的数组,求f[5]的过程是这样的:

  1. 自己作为一个子序列,值为$1$
  2. 接在$a[1]$后面,值为$f[1]+1$
  3. 接在$a[2]$后面,值为$f[2]+1$
  4. 接在$a[4]$后面,值为$f[4]+1$

看到这里应该可以知道,要求出$f[x]$,只需要知道$a[x]$能接到哪些数的后面,所以我们可以得到式子:

$$ f[x]=max\left \{ f[p]+1 \right \}(p<x,a[p]<a[x]) $$

其中初始条件是$f[1]=1$

1.5 转移

在前面的三个问题中,先是设计好了状态,再给出了由小状态求大状态的方法。从一个状态的解得到另一个状态的解称为“状态转移”,状态转移的式子称为“状态转移方程”。

在设计转移的时候,考虑的都是“这个局面是从哪过来的”,这是转移的一种思路:当前状态的解未知,需要用已经解决的状态推出。称为“从哪来”。

另一种转移思路是:当前状态的解已知,利用这个解,推出其他状态的解。称为“从哪去

1.6 两种转移方式

下面给出前面三个问题的两种转移方式的实现代码。

  • 例1.6.1
//台阶问题-从哪来

cin>>n;
f[1]=1; f[2]=2;
for (int i=3;i<=n;i++)
    f[i]=f[i-1]+f[i-2];
cout<<f[n]<<'\n';
  • 例1.6.2
//台阶问题-从哪去

cin>>n;
f[0]=1;  
for (int i=0;i<=n;i++)    //会超一点范围
{
    f[i+1]+=f[i];    //走一级或走两级
    f[i+2]+=f[i];
}
cout<<f[n]<<'\n';
  • 例1.6.3
// 硬币问题-从哪来

cin>>n;
memset(f,0x3f,sizeof(f));    //用了min,所以要赋大点的值
f[0]=0;
for (int i=1;i<=n;i++)
{
    f[i]=min(f[i],f[i-1]+1);
    if (i>=5) f[i]=min(f[i],f[i-5]+1);
    if (i>=11) f[i]=min(f[i],f[i-11]+1);
}
cout<<f[n]<<'\n';

注:0x3f一般可把可修改的左值设为较大的int值。

  • 例1.6.4
// 硬币问题-从哪去

cin>>n;
memset(f,0x3f,sizeof(f));    //用了min,所以要赋大点的值
f[0]=0;
for (int i=0;i<=n;i++)    //会超出一点范围
{
    f[i+1]=min(f[i+1],f[i]+1);
    f[i+5]=min(f[i+5],f[i]+1);
    f[i+11]=min(f[i+11],f[i]+1);
}
cout<<f[n]<<'\n';
  • 例1.6.5
//最长上升子序列-从哪来

cin>>n;
for (int i=1;i<=n;i++)
    cin>>a[i];
    
f[1]=1;
for (int i=2;i<=n;i++)
    for (int j=1;j<i;j++)
        if (a[j]<a[i]) f[i]=max(f[i],f[j]+1);

int maxn=0;
for (int i=1;i<=n;i++)
    maxn=max(maxn,f[i]);
cout<<maxn<<'\n';
  • 例1.6.6
//最长上升子序列-从哪去

cin>>n;
for (int i=1;i<=n;i++)
    cin>>a[i];
    
f[1]=1;
for (int i=1;i<n;i++)
    for (int j=i+1;j<=n;j++)
        if (a[i]<a[j]) f[j]=max(f[j],f[i]+1);

int maxn=0;
for (int i=1;i<=n;i++)
    maxn=max(maxn,f[i]);
cout<<maxn<<'\n';

1.7 动态规划总结

如果用动态规划来解决一个题目,你需要如下的“三连”:

  1. 设计状态:要选择出正确的状态。
  2. 得出转移方程:最难也是最重要的一步。
  3. 考虑如何实现(从哪来,从哪去)

决策类的动态规划,设计状态时,需要满足两个原则:

  1. 最优子结构:大问题的最优解,一定是由小问题的最优解推出来的。
  2. 无后效性:现在的决策,只与过去的结果有关,与过去的决策无关。

1.8 记忆化搜索

文章“递推与递归”的2.4 实例-求斐波那契数(一)*中提到过了记忆化。记忆化可以减少递归过程中的重复计算,大大降低时间复杂度。记忆化的基本操作如下:

  1. 如果该值未被计算,则计算出该值后存储该值并使用。
  2. 如果该值被计算过,直接使用存储的值。

一般而言,当计算出的值不会为0时,我们用元素的值是否为0来判断是否被计算,如果会为0的话,则需要新建一个vis数组来判断该值是否被计算过。

再贴一次代码。

  • 例1.8.1
int vis[1000005];    //如果求出的f[n]值为0时需要使用vis
int f[1000005];
long long Fibonacci(int n)
{
    if (n<=1) return 1;
    if (!f[n]) 
    	f[n]=Fibonacci(n-1)+Fibonacci(n-2)
    return f[n];
}

一个例题,try一下。

2 背包问题

2.1 01背包

  • 问题:现在有$n$个物品,第$i(1 \leq i \leq n)$个物品的体积为$v[i]$,价值为$w[i]$,你有一个背包,容量为$V$,请求出这些物品可以达到的最大总价值,并且体积总和不超过背包容量

如何解决这个问题?我们首先应该设计状态,如何设计?应当这样设计:创建一个二维数组$dp$,$dp[i][j]$表示只考虑前$i$个物品,用$j$的容量能装下的最大值

如何设计转移?应当这样设计,转移方程为:

$$ dp[i][j]=max\left\{\begin{matrix} dp[i-1][j]\\ dp[i-1][j-v[i]]+w[i] \end{matrix}\right. $$

等等,是不是太快了?没关系,请你先看一遍记住它。接下来进行一层一层的解答。

为什么$i$表示考虑前$i$个物品?因为这样每个物品都只会被取一次,并且不用知道前面取了哪个物品,保证了其无后效性,满足动态规划的要求。

转移方程怎么解释?到达$dp[i][j]$有两种方式,要么就是取了第$i$个物品,要么就是没取第$i$个物品,我们只需要找到这两种方式里面最优的选择就可以了。

那么用什么方法去实现?因为它是二维的,所以最好的方法就是用递推去做,代码如下。

  • 例2.1.1
int n,m;    //n为物品数量,m为容量
cin>>n>>m;

for (int i=1;i<=n;i++)
    cin>>w[i]>>v[i];    //输入物品的价值和体积

for (int i=1;i<=n;i++)
    for (int j=0;j<=m;j++)
    {
        dp[i][j]=dp[i-1][j];

        if (j-v[i]>=0)    //可以装
            dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
    }
    
int maxn=0;
for (int i=1;i<=n;i++)    //找价值最大的
    maxn=max(maxn,dp[i][m]);

这类的关于“求一定容量下‘背包’能装的最大价值”的问题叫做背包问题,由于这个问题的物品只可以取1次或0次,所以这个也叫做01背包问题

2.2 01背包的空间优化

回顾一下上面的转移方程:

$$ dp[i][j]=max\left\{\begin{matrix} dp[i-1][j]\\ dp[i-1][j-v[i]]+w[i] \end{matrix}\right. $$

可以发现$dp[1][...]$,$dp[2][...]$等等过去了就永远不会被再次访问到,这就造成了空间的浪费,我们需要开一个大数组去维持。所以或许需要空间上优化一下。

可以注意到$dp[i][...]$只与$dp[i-1][...]$有关,也就是当前的状态只与前一状态剩余的容量有关,所以这个第一维我们可以去掉。改进一下例4.1.1,就可以得到下面的代码:

  • 例2.2.1
for (int i=1;i<=n;i++)
    for (int j=0;j<=m;j++)
        if (j-v[i]>=0)
            dp[j]=max(dp[j],dp[j-v[i]]+wi);

看起来非常的nice,但是一运行,这是什么鬼🙃?怎么得出来的是错误答案?

仔细想想为什么?我们一步一步来看,假设现在的i=4,数组dp里面的内容是[4 5 6 8 9],这第$i$个物品的重量为2,价值为3。现在按照循环来模拟:

  1. j=0:[4 5 6 8 9]
  2. j=1: [4 5 6 8 9]
  3. j=2:[4 5 7 8 9]——这时满足条件,4+3=7
  4. j=3: [4 5 7 8 9]——满足条件,5+3=8
  5. j=4:[4 5 7 8 10]——满足条件,7+3=10,可是这时候用了已经更新过的值!

错误就是在这里,因为满足条件时是向前取值。因为是向前取值,如果我们把顺序倒过来,那么向前取值一定不会取到已经更新的值,改进后的代码如下:

  • 例2.2.2
for (int i=1;i<=n;i++)
    for (int j=m;j>=0;j--)
        if (j-v[i]>=0)
            dp[j]=max(dp[j],dp[j-v[i]]+wi);

这样,我们就完成了01背包的空间优化

2.3完全背包和完全背包的空间优化

  • 问题:有$n$种物品和一个容量为$V$的背包,每种物品都就可以选择任意多个,第$i$个物品的价值为w[i],体积为v[i],请求出这些物品可以达到的最大总价值,并且体积总和不超过背包容量。

这个问题和01背包问题只有一点不同,就是每个物品可以选择任意多次。可能最直接的就想到贪心算法:因为每个物品都可以选择任意多次,在容量允许的情况下,每次都取性价比最高的物品,这样我们就可以得到答案了!

但遗憾的告诉你,这样的程序是不好想的,给出一组数据n=2,V=10,w[5,7],v[5,6],这样第一次选了w=7,v=6,因为这样性价比高,但是选完后就不能选其他物品了。你使用贪心需要更多的处理。

接着来说正确的做法。我们可以参考一下01背包是怎么做的。01背包问题为什么能使得只取一次?因为$dp[i][...]$只跟$dp[i-1][...]$有关,也就是取不取第i个物品,但是如果$dp[i][...]$跟dp[i][...]有关呢?那么我们就可以使得第i个物品重复被取。有了这个基础就可以写出状态和转移方程了。

状态:创建一个二维数组$dp$,$dp[i][j]$表示只考虑前$i$个物品,用$j$的容量能装下的最大值

转移方程:

$$ dp[i][j]=max\left\{\begin{matrix} dp[i-1][j]\\ dp[i][j-v[i]]+w[i] \end{matrix}\right. $$

得出状态和转移方程之后我们就可以写代码了,代码如下:

  • 例2.3.1
int n,m;    //n为物品数量,m为容量
cin>>n>>m;

for (int i=1;i<=n;i++)
    cin>>w[i]>>v[i];    //输入物品的价值和体积

for (int i=1;i<=n;i++)
    for (int j=0;j<=m;j++)
    {
        dp[i][j]=dp[i-1][j];

        if (j-v[i]>=0)    //可以装
        dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);    //注意这里
    }
    
int maxn=0;
for (int i=1;i<=n;i++)    //找价值最大的
    maxn=max(maxn,dp[i][m]);
cout<<maxn<<'\n';

请注意了,第二层循环不可以倒着写,为什么?因为$dp[i][...]$与$dp[i][...]$有关,我们需要用已经更新过的值去更新。这和01背包是不一样的,可以作为它们的最大区别。没有空间优化的01背包正序倒序都可以做出来,因为$dp[i][...]$只与$dp[i-1][...]$有关。

所以空间优化时就按正序来更新,而不是倒序。代码如下。

  • 例2.3.2
for (int i=1;i<=m;i++)
    for (int j=0;j<=t;j++)
        if (j-v[i]>=0)
            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);

这样的问题就是完全背包问题

2.4 多重背包

  • 问题:有$n$种物品和一个容量为$V$的背包。第$i$种物品最多有$n[i]$件可用,每件物品体积是$v[i]$,价值是$w[i]$。请求出这些物品可以达到的最大总价值,并且体积总和不超过背包容量。

由于已经给定了可以用的物品数量,所以可以把第$i$个物品想象成是$i*n[i]$个物品,这样问题就变成了01背包问题,直接用01背包问题的解法来做。

这样的问题就是多重背包问题


感谢浏览😝!

此文章可能会在后续更新,欢迎纠错。