搜索

C++ 动态规划:一维动态规划,背包问题,区间动态规划


发布时间: 2022-11-24 21:37:01    浏览次数:29 次

C++ 动态规划


动态规划的定义


动态规划(Dynamic Programming,DP)是运筹学的一个分支,是求解决策过程最优化的过程。动态规划是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。简单来说动态规划其实就是,给定一个问题,我们把它拆成一个个子问题,直到子问题可以直接解决。然后呢,把子问题答案保存起来,以减少重复计算。再根据子问题答案反推,得出原问题解的一种方法。

动态规划的基本思想


动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样,但它们具有相同的填表格式。
动态规划最核心的思想,就在于拆分子问题,记住过往,减少重复计算。

一维动态规划


示例:

【题目描述】
一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级台阶。求该青蛙跳上一个 10 级的台阶总共有多少种跳法

要想跳到第 10 级台阶,要么是先跳到第 9 级,然后再跳 1 级台阶上去;要么是先
跳到第 8 级,然后一次迈 2 级台阶上去。同理,要想跳到第 9 级台阶,要么是先跳到第 8 级,然后再跳 1 级台阶上去;要么是先跳到第 7 级,然后一次迈 2 级台阶上去。要想跳到第 8 级台阶,要么是先跳到第 7 级,然后再跳 1 级台阶上去;要么是先跳到第 6 级,然后一次迈 2 级台阶上去。
假设跳到第 n 级台阶的跳数我们定义为 f(n),很显然就可以得出以下公式:
F(10) = f(9)+f(8)
f (9) = f(8) + f(7)
f (8) = f(7) + f(6)
...
f(3) = f(2) + f(1)
即通用公式为: f(n) = f(n-1) + f(n-2)
那 f(2) 或者 f(1) 等于多少呢?
当只有 2 级台阶时,有两种跳法,第一种是直接跳两级,第二种是先跳一级,然后再跳一
级。即 f(2) = 2;当只有 1 级台阶时,只有一种跳法,即 f(1)= 1;

这样就可以用递归算法解决因此,青蛙跳阶,递归解法的时间复杂度 = O(1) * O(2^n) = O(2^n),就是指数级别的,爆炸增长的,如果 n 比较大的话,超时很正常的了。
回过头来,你仔细观察这颗递归树,你会发现存在大量重复计算,比如 f(8)被计算
了两次,f(7)被重复计算了 3 次...所以这个递归算法低效的原因,就是存在大量的重复
计算!

既然存在大量重复计算,那么我们可以先把计算好的答案存下来,即造一个备忘录,等到下次需要的话,先去备忘录查一下,如果有,就直接取就好了,备忘录没有才开始计算,那就可以省去重新重复计算的耗时啦!这就是带备忘录的解法。

使用动态规划解法如下:

///关键代码:
int dp[10005];
dp[1]=1;
dp[2]=2;
int numWays(int n) {
for (int i = 3; i <= n; i++) {
dp[i] = (dp[i-1] + dp[i-2]);   //状态转移方程
}
return dp[n];
}

f(n-1)和 f(n-2) 称为 f(n) 的最优子结构
f(n)= f(n-1)+f(n-2) 就称为状态转移方程
f(1) = 1, f(2) = 2 是边界
比如 f(10)= f(9)+f(8),f(9) = f(8) + f(7) ,f(8)就是重叠子问题

动态规划的解题思路如下:
1.穷举分析
2.确定边界
3.找出规律,确定最优子结构
4.写出状态转移方程


背包类型动态规划


背包问题的定义:

背包问题(Knapsack problem)是一种组合优化的 NP 完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学,计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题,即在总重量不超过 W 的前提下,总价值是否能达到 V?它是在 1978 年由 Merkle 和 Hellman 提出的,定义如下:我们有 n 种物品,物品 j 的重量为 wj,价格为 pj。我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为 W。如果限定每种物品只能选择 0 个或 1 个,则问题称为 0-1 背包问题。

背包问题的原理:

动态规划与分治法类似,都是把大问题拆分成小问题,通过寻找大问题与小问题的递推关系,解决一个个小问题,最终达到解决原问题的效果。但不同的是,分治法在子问题和子子问题等上被重复计算了很多次,而动态规划则具有记忆性,通过填写表把所有已经解决的子问题答案纪录下来,在新问题里需要用到的子问题可以直接提取,避免了重复计算,从而节约了时间,所以在问题满足最优性原理之后,用动态规划解决问题的核心就在于填表,表填写完毕,最优解也就找到。

背包问题的分类

背包问题可以总结为三类:01 背包问题、完全背包问题以及分组背包问题。
01 背包问题:每个元素最多取 1 次。具体来讲:一共有 N 件物品,第 i(i 从 1 开
始)件物品的重量为 w[i],价值为 v[i]。在总重量不超过背包承载上限 W 的情况下,能
够装入背包的最大价值是多少?
完全背包问题:每个元素可以取多次。具体来讲:完全背包与 01 背包不同就是每种
物品可以有无限多个:一共有 N 种物品,每种物品有无限多个,第 i(i 从 1 开始)种
物品的重量为 w[i],价值为 v[i]。在总重量不超过背包承载上限 W 的情况下,能够装入
背包的最大价值是多少?
分组背包问题:有多个背包,需要对每个背包放入物品,每个背包的处理情况与完全
背包完全相同。
在完全背包问题当中根据是否需要考虑排列组合问题(是否考虑物品顺序),可分为
两种情况,我们可以通过内外循环的调换来处理排列组合问题,如果题目不是排列组合问
题,则这两种方法都可以使用(推荐使用组合来解决)
而每个背包问题要求的也是不同的,按照所求问题分类,又可以分为以下几种:
1、最值问题:要求最大值/最小值
2、存在问题:是否存在…………,满足…………
3、组合问题:求所有满足……的排列组合

解题模板:

1.01 背包问题

【题目描述】
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。
【输入格式】
第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。
接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。
【输出格式】
输出一个整数,表示最大价值。
【思路解析】
「01 背包」是指给定物品价值与体积(对应了「给定价值与成本」),在规定容量下
(对应了「限定决策规则」)如何使得所选物品的总价值最大。
1.01 背包是动态规划类问题。一般需要将主问题分解为多个子问题,然后记录下不
同子问题的解,最终才能推得最终问题的答案。
2.定义子问题:前 i 件物品恰放入一个容量为 v 的背包可以获得的最大价值是多少?
3.我们用 f[i][v] 表示 前 i 件物 恰放入一个 容量为 v 的背包可以获得的 最大价值。
4.要求主问题 f[i][v] 就得先知道子问题 F[i-1][v]和 f[i-1][ v-v[i] ]是多少 。然后通过状
态转移方程:f[i][v]=max{ f[i-1][v] , f[i-1][ v-v[i] ]+c[i]] }
5.状态转移方程是整个背包问题的核心。解释:“前 i 个物品放入容量为 v 的背包中”
可以转化为“前 i-1 个物品已经放入了容量为 v 的背包中(即为 f[i-1][v])” 和 “第 i 个物品
放还是不放入背包中?”
 如果第 i 个物品不放入背包,那么 f[i][v]=f[i-1][v]
 如果第 i 个物品放入背包,那么 f[i][v]=f[i-1][ v-v[i] ] + c[i],此时这个式子里面只有
f[i-1][ v-v[i] ]未知,问题转化为“前 i-1 个物品放入了剩余容量为 v-v[i]的背包中能获
得最大价值是多少?
代码实现:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxN=1010;
int f[maxN][maxN];                  //f[i][j]体积为 j 的背包在前 i 件物品中能装的最大价值
int v[maxN];                        //物品体积
int w[maxN];                        //物品价值
int main()
{
int n,m;
memset(f,0,sizeof(f));
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d %d",&v[i],&w[i]);            //各物品价值
}
//计算所有子问题的答案。
for(int i = 1;i <= n; i++){
for(int j = 0;j <= m; j++){
f[i][j]=f[i-1][j];                          //体积为 i-1 可以拿 f[i-1][j], 那体积比它大的 i 的至少也可以拿它那么多吧
if(j >= v[i])                               // 防止 f[j-v[i]]越界
f[i][j] = max(f[i-1][j] , f[i-1][j - v[i]] + w[i]);
}
}
printf("%d\n",f[n][m]);
return 0;
}
2.完全背包

【题目描述】
有 n 种物品和一个容量为 c 的背包,每种物品都有无限件。
第 i 件物品的体积是 v[i],价值是 w[i]。
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
【输入样例】
2 5
1 1
2 2
【输出样例】
5
解释:选一件物品 1,再选两件物品 2,可使价值最大 。
【思路解析】
我们可以直接将 01 背包的「状态定义」拿过来用:
dp[i][j]代表考虑前 i 件物品,放入一个容量为 j 的背包可以获得的最大价值。
由于每件物品可以被选择多次,因此对于某个 dp[i][j] 而言,其值应该为以下所有可
能方案中的最大值:
选择 0 件物品 i 的最大价值,即 dp[i-1][j]
选择 1 件物品 i 的最大价值,即 dp[i-1][j-v[i]]+w[i]
选择 2 件物品 i 的最大价值,即 dp[i-1][j-2v[i]]+2w[i]
...
选择 k 件物品 i 的最大价值,dp[i-1][j-kv[i]]+kw[i]
由此我们可以得出「状态转移方程」为:
dp[i][j] = max(dp[i-1][j],dp[i-1][j-2v[i]]+2w[i]), 0<k*v[i]≤j
代码实现

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxN=1010;
int f[maxN][maxN];   //f[i][j]体积为 j 的背包在前 i 件物品中能装的最大价值
int v[maxN];         //物品体积
int w[maxN];        //物品价值
int main()
{
int n,c;
memset(f,0,sizeof(f));
scanf("%d %d",&n,&c);
for(int i=0;i<n;i++){
scanf("%d %d",&v[i],&w[i]);        //各物品价值
}
// 先预处理第一件物品
for (int j = 0; j <= c; j++) {
                                  // 显然当只有一件物品的时候,在容量允许的情况下,能选多少件就选多少件
int maxK = j / v[0];
f[0][j] = maxK * w[0];
}
for (int i = 1; i < n; i++) {
for (int j = 0; j <= c; j++) {
               // 不考虑第 i 件物品的情况(选择 0 件物品 i)
int x = f[i - 1][j];
              // 考虑第 i 件物品的情况
int y = 0;
int k=1;           //选择第 i 件物品的数量
while(j >= v[i] * k){
y = max(y, f[i - 1][j - k * v[i]] + k * w[i]);
k++;
}
f[i][j] = max(x, y);
}
}
printf("%d\n",f[n-1][c]);
return 0;
}

区间动态规划

区间动态规划定义:

区间类动态规划是线性动态规划的拓展,它在分阶段划分问题时,与阶段中元素出现
的顺序和由前一阶段的哪些元素合并而来有很大的关系。如状态 f[i][j],它表示以已合并的
次数为阶段、以区间的左端点 i 为状态,它的值取决于第 i 个元素和第 j 个元素断开的位置
k,即 f[i][k]+f[k+1][j]的值。这一类型的动态规划,阶段特征非常明显,求最优值时需要预
先设置阶段内的区间统计值,还要以动态规划的起始位置来判断。
区间类动态规划的特点:
合并:即将两个或多个部分进行整合,当然也可以反过来,也就是对一个问题分解成
两个或多个部分。
特征:对将问题分解成为两两合并的形式。
求解:对整个问题设最优值、枚举合并点,将问题分解成左右两个部分,最后合并左
右两个部分的最优值得到原问题的最优值。有点类似分治算法的解题思想。
区间类动态规划的典型应用有:石子合并、能量项链、凸多边形的划分等。
区间型 DP 中的区间通常指的就是字面意义上的区间,以一组数列为例,那么[i][j]表示
的就是 i 到 j 的这个区间。
区间型动态规划的递归关系,通常是呈现出去头去尾的特点,以下面的伪代码为例。
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) //区间[i][j]由去掉头(或者去掉尾)的[i + 1][j](dp[i][j - 1])推

基于此种特性,区间型 DP 的代码实现通常要对区间长度进行循环,即从区间长度短
的循环到区间长度长的,当求当前状态的值的时由于使用到的子状态的区间长度都小于当
前状态,因此都可以推出,非常的合理且符合直觉。

伪代码:
for (int i = 1; i <= len; i++)               //循环区间长度
for (int j = 0; j <= n - len; j++)            //循环做端点
for (int z = j + 1; z < n; z++)              //循环右端点
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);          //转移方程

例题解析:石子合并
【题目描述】
将 n 堆石子绕圆形操场排放,现要将石子有序地合并成一堆。规定每次只能选相邻的
两堆合并成新的一堆,并将新的一堆的石子数记做该次合并的得分。
请编写一个程序,读入堆数 n 及每堆的石子数,并进行如下计算:
选择一种合并石子的方案,使得做 n-1 次合并得分总和最大。
选择一种合并石子的方案,使得做 n−1 次合并得分总和最小。
【输入格式】
输入第一行一个整数 n,表示有 n 堆石子。
第二行 n 个整数,表示每堆石子的数量。
【输出格式】
输出共两行:
第一行为合并得分总和最小值,
第二行为合并得分总和最大值。
【输入样例】
4
4 5 9 4
【输出样例】
43
54
数据范围与提示
对于 100%的数据,有 1≤n≤200。
【思路解析】
最初的第 l 堆石子和第 r 堆石子被合并成一堆,则说明 l~r 之间的每堆石子也已经被
合并,这样 l 和 r 才有可能相邻。因此,在任意时刻,任意一堆石子均可以用一个闭区间
[l,r]来描述,表示这堆石子是由最初的第 l~r 堆石子合并而成的,其重量为∑ai(l≤i≤r)。
另外,一定存在一个整数 k(l≤k<r),在这堆石子形成之前,先有第 l~k 堆石子(闭区间[l,k])
被合并成一堆,第 k+1~r 堆石子(闭区间[k+1,r])被合并成一堆,然后这两堆石子才合并成
[l,r]。
对应到动态规划中,就意味着两个长度较小的区间上的信息向一个更长的区间发生了
转移,划分点 k 就是转移的决策。自然地,应该把区间长度 len 作为 DP 的阶段。不过,区
间长度可以由左端点和右端点表示,即 len=r-l+1。本着动态规划“选择最小的能覆盖状态
空间的维度集合”的思想,我们可以只用左、右端点表示 DP 的状态。
设 sum[i]表示从第 l 堆到第 i 堆石子数总和 sum[i]=a[1]+a[2]…+a[i]。
Fmax[i][j]表示从第 i 堆石子合并到第 j 堆石子的最大的得分。
Fmin[i][j]表示从第 i 堆石子合并到第 j 堆石子的最小的得分。
则状态转移方程为:
Fmax[i][j]=max{Fmax[i][k]+Fmax[k+1][j]+sum[j]-sum[i-1]}(i≤k≤j-1).
Fmin[i][j]=min(Fmin[i][k]+Fmin[k+1][j]+sum[j]-sum[i-1])(i≤k≤j-1)
初始条件:Fmax[i][i]=0,Fmin[i][i]=INF。
时间复杂度为 O(n³)。
代码实现

#include <iostream>
using namespace std;
const int maxn=205,inf=0x7fffffff/2;
int f1[maxn][maxn],f2[maxn][maxn],s[maxn][maxn]={0};
int a[maxn],sum[maxn]={0},n,ans1,ans2;
void dp(){
for(int l=2;l<=n;l++){
for(int i=1;i<=2*n-l+1;i++){
int j=i+l-1;
f1[i][j]=inf;
f2[i][j]=0;
for(int k=i;k<j;k++){
f1[i][j]=min(f1[i][j],f1[i][k]+f1[k+1][j]);
f2[i][j]=max(f2[i][j],f2[i][k]+f2[k+1][j]);
}
f1[i][j]+=sum[j]-sum[i-1];
f2[i][j]+=sum[j]-sum[i-1];
}

}
ans1=inf,ans2=0;
for(int i=1;i<=n;i++)
ans1=min(ans1,f1[i][i+n-1]);
for(int i=1;i<=n;i++)
ans2=max(ans2,f2[i][i+n-1]);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
a[i+n]=a[i];
}
for(int i=1;i<=n*2;i++){
sum[i]=sum[i-1]+a[i];
f2[i][i]=0;
f1[i][i]=0;
}
dp();
printf("%d\n%d\n",ans1,ans2);
return 0;
}
以上便是这篇文章的所有内容,希望对你有帮助。~~
免责声明 C++ 动态规划:一维动态规划,背包问题,区间动态规划,资源类别:文本, 浏览次数:29 次, 文件大小:-- , 由本站蜘蛛搜索收录2022-11-24 09:37:01。此页面由程序自动采集,只作交流和学习使用,本站不储存任何资源文件,如有侵权内容请联系我们举报删除, 感谢您对本站的支持。 原文链接:https://www.cnblogs.com/demc/p/16914911.html