讲义 GDFZOJ 【37】动态规划基础2

动态规划基础2

【传送门】

T1 01背包

洛谷原模板题戳这儿

这是一道(Dp)的模板题，也没什么好说的，直接开始吧

一、审题

有N件物品和一个容量为(V)的背包。第(i)件物品所占空间是(C_i)，价值是(W_i)。求解将哪些物品装入背包可使价值总和最大。

数据范围：(0 le V le 1000,0le Nle 100,0 < C le 1000,0 < W le 100)

似乎并没有什么关键点，粗略判断时间复杂度，(emm······)，(O(NV))是可以过的，那就往这方面想吧

贪心

若果你还没学过(Dp)，就很容易会想到用贪心来做这道题，设一个数组(sum_i=dfrac{W_i}{C_i})，然后优先但是就会出现一个很大的问题：假设我们背包的容量(C=10)，有以下三个物品

物品编号	A	B	C
(C)	6	5	5
(W)	9	6	6
(Sum)	1.5	1.2	1.2

根据以上的贪心策略，我们应该是要选(A)的，但是我们发现同时选(B)和(C)的话得到的价值会更大呀，贪心思想不能从大局考虑，所以必须要用(Dp)

背包

既然确定了是动规，那就可以愉快地开始推式子啦

让我假设现在的背包的容量C=10；

物品编号	物品重量	物品价值
1	5	20
2	6	10
3	4	12

我们用(v[i])表示物品价值，(w[i])表示物品重量，再首先定义状态$ dp[i][j](以)j$ 为容量为放入前(i)个物品(按(i)从小到大的顺序)的最大价值，那么 (i=1)的时候，放入的是物品(1)，这时候肯定是最优的啦！

那考虑一下当前容量(j)，如果 (j<5)，那么肯定就不能放，所以(dp[1][j]=0(j lt 5))；那如果 (j>5)，那就可以放进去了的呀，所以(dp[1][j]=20(j>=5))；

接着 i=2i=2 放两个物品，求的就是 (dp[2][j]) 了，当 (j<5)的时候，是不是同样的 (dp[2][j](j lt 5)=0)；那当 (j<6) 是不是还是放不下第二个，只能放第一个；

那 (j>6) 呢？是不是就可以放第二个了呢？是可以，但是明显不是最优的，用脑子想了一下，发现 (dp[2][j](j gt 6)=20)，这个 (20)怎么来的呢，当然是从前一个状态来的（注意这里就可以分为两种情况了）：一种是选择第二个物品放入，另一种还是选择前面的物品；

我们假设(j=10)，这时候：(dp[2][10]=max((dp[1][10-w[2]])+v[2],dp[1][10]))也就是(dp[2][10] = max(dp[1][4])+10,dp[1][10]))

是不是很明显了呢，(dp[1][4]+10)是选择了第二个，于是容量相应就减少成 (4)，之前已经得出 (dp[1][4]=0)，就是说选了物品(2)，物品(1)就选不了了；(dp[1][10])是不选择第二个，只选择第一个(dp[1][10])是等于(20)的，于是得出(dp[2][10]=20)

到这里就可以了，依次类推，动态转移方程为

[dp[i][j] = max(dp[i-1][j-w[i]])+v[i],dp[i-1][j] ]

但是好像还有一些问题没考虑完(......)

2、需要单独考虑的问题

看回例子：

物品编号	物品重量	物品价值
1	5	20
2	6	10
3	4	12

我们知道 (dp[1][j](j lt 5)=20),那么 (dp[2][j](j=5)) 的时候是多少呢？我们看到动态转移方程并没有考虑 (jlt w[i]) 的情况，但是我们可以加进去，由于我们可以看出来(dp[2][5]=5)，为什么？因为不能选第二个，只能选第一个，所以(dp[2][5]=dp[1][5])了！所以当(j<w[i])的时候，(dp[i][j]=dp[i-1][j])就好了，是不是很神奇呢?

一维优化

我们刚是用二维来存状态的，那可不可以压缩到一维呢？

答案是可以的，其实我们发现上面的(i)是可以省去的，但这个时候就会有人说了：物品会重复放入。所以重点就是，一维内层循环要倒着来！不然会重复放入

T2 完全背包

GDFZOJ原题地址戳这儿

洛谷原模板题戳这儿

这是一道(Dp)的模板题，也没什么好说的，直接开始吧

有N件物品和一个容量为(V)的背包。每种物品均有无穷多件，第(i)件物品所占空间是(C_i)，价值是(W_i)。求解将哪些物品装入背包可使价值总和最大。

数据范围：(0 le V le 1000,0le Nle 100,0 < C le 1000,0 < W le 100)

似乎并没有什么关键点，粗略判断时间复杂度，(emm······)，(O(NV))是可以过的，那就往这方面想吧

我们发现这道题是不是和这道题与这道题很像？是的这两道题之间的差异只在这一句话( ext{“每种物品均有无穷多件”})，所以可以推断出这道题的式子一定和上一道题很像，所以建议先看一看上一题的题解

在上一篇题解里我们在一维数组中说到( ext{重点就是，一维内层循环要倒着来！不然会重复})，这是在01背包中需要做的，但是在这里就不需要了呀，反正每种物品都有无穷多件，为什么要考虑重合呢？

所以直接从小到大枚举就行啦！！！

T3 多重背包

这是一道(Dp)的模板题，也没什么好说的，直接开始吧

有N件物品和一个容量为(V)的背包。每种物品均有有限多件，第(i)件物品所占空间是(C_i)，价值是(W_i)。求解将哪些物品装入背包可使价值总和最大。

数据范围：(0 le V le 1000,0le Nle 100,0 < C le 1000,0 < W le 100)

似乎并没有什么关键点，粗略判断时间复杂度，(emm······)，(O(NV))是可以过的，那就往这方面想吧

我们发现这道题是不是和这道题、这道题很像？是的这两道题之间的差异只在这一句话( ext{“每种物品均有有限多件”})，所以可以推断出这道题的式子一定和上一道题很像，所以建议先看一看上一题的题解

其实这也不是很简单吗？既然他有有限个物品，那把它转化为多个一样的物品不就做出来了吗？所以只需要在(01)背包的基础上再加上预处理就行啦

还不会(01)背包的人戳这儿

T4 过河卒

GDFZOJ原题地址戳这儿

洛谷原题地址戳这儿

(A)点有一个过河卒，需要走到目标(B)点。卒行走规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如上图的(C)点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图(C)点上的马可以控制(9)个点（图中的(P1,P2…P8)和(C)）。卒不能通过对方马的控制点。

棋盘用坐标表示，(A) 点((0,0))、(B)点((n,m))（(n,m)为不超过(20)的整数)，同样马的位置坐标是需要给出的。现在要求你计算出卒从(A)点能够到达(B)点的路径的条数。

很明显，这道题用暴搜是不行的，所以要用(Dp)

我们首先定义状态，我们设(f_{i,j})为从点((0,0))走到点((i,j))一共有多少种方案，然后就可以开始愉快地推式子啦

首先我们知道(f_{i,j})可以从(f_{i-1,j})和(f_{i,j-1})转移过来，因为如果要走到点((i,j))，就一定要么要经过((i-1,j))，要么要经过((i,j-1))，而且只能从这两个点走过来。所以我们可以很容易就推出一个式子:

[f_{i,j}=f_{i-1,j}+f_{i,j-1} ]

可是我们还有“马”没有处理呢！其实这个也很简单，因为没法走到被马控制的点，所以只需要针对马控制的点((i,j))，将(f_{i,j})改为(0)就行了

所以我们就顺利地推出来了

[f_{i,j}=egin{cases}f_{i,j-1}+f_{i-1,j}&( ext{点}(i,j) ext{不为被马控制的点})\0&( ext{点}(i,j) ext{为被马控制的点})end{cases} ]

T5 邮票问题

给定一个信封，最多只允许粘贴(n(nle100))张邮票，我们现在有(m(mle100))种邮票，面值分别为：(x_1,x_2,······,x_m(xile255, ext{为正整数}))分，并假设各种邮票都有足够多张。要求计算所能获得的邮资最大范围。即求最大值(MAX)，使在(1-MAX)之间的每一个邮资值都能得到。

很明显，这是一道(Dp)的题目

我们先定义一个状态(f_j)表示要凑到面值为(j)分的邮票最少需要多少张邮票，容易得到，若果我们有一张面值为(x)的邮票，那么(f_j=f_{j-x}+1)，不过有可能这并不是最优的解法呀，所以我们需要取一个(max)，于是我们的式子就这么简单地推出来了:

[f_j=max(f_j,f_{j-x}+1) ]

T6 骑士游历

我们考虑一个点能在哪个点跳过来，设当前点的坐标是((x,y))，则能在点((x-2,y-1),(x-2,y+1),(x-1,y-2),(x-1,y+2))跳过去。

那么就很容易想到，设(f[x][y])表示从起点到点((x,y))的方案数，状态转移方程为：(f[x][y] = f[x - 2][y - 1] + f[x - 2][y + 1] + f[x - 1][y - 2], f[x - 1][y + 2])。

需要注意的是，要判断数组越界(国际惯例)，本题坐标从左下角开始，答案要开(long long)。

[ ext{十年OI一场空，不开longlong见祖宗} ]

T7 乘积最大

~~这题数据很水，可以直接dfs~~

首先，因为输入的是一个字符串，我们先将字符串转化成一个数组。设(a[i][j])表示截取第i个数字到第j个数字所表示的数值。

然后，~~因为这题是一道区间dp，所以~~我们设(f[i][j])表示前i位插入(j)个乘号所得到的最大值。

很容易想到初始数值是前i位如果不插入乘号，那么答案就是前i位表示的数值，即(f[i][0] = a[0][i])。

最后，状态转移方程为(f[i][j] = max(f[pos][j-1] * a[pos + 1][i],f[i][j]))，其中(f[pos][j - 1] * a[pos + 1][i])表示在第(pos)个数字和第(pos + 1)个数字之间插入一个乘号时的最大值。((pos)从(0)到(i - 1))