前言
和分治法一样,动态规划(dynamic programing)是通过组合子问题的解而解决整个问题的。注意这里的programing翻译成立规划而不是编程。维基百科上写道
This is also usually done in atabular formby iteratively generating solutions to bigger and bigger subproblems by using the solutions to small subproblems.
这说明动规的关键是table,是子问题。而且动规的子问题是相互关联的。而分治算法是将问题划分成相对独立的子问题,递归的解决所有子问题,
然后合并子问题成为最终的结果。在这个过程中,分治法会做很多不必要的工作,即重复地求解公共子问题。
动规对每个子问题之求解一遍,并且将其结果保存在表中,从而避免了子问题被重复计算。
适用范围
1.动态规划通常情况下应用于最优化问题,这类问题一般有很多个可行的解,每个解有一个值,而我们希望从中找到最优的答案。
2.该问题必须符合无后效性。即当前状态是历史的完全总结,过程的演变不再受此前各种状态及决策的影响。
简单动态规划问题
最大子数组和问题
题目
一个有N个整数元素的一位数组(A[0], A[1],...,A[n-1], A[n]),这个数组当然有很多子数组,那么数组之和的最大值是什么呢?
这是一道很简单的题目,但是要想写出时间复杂度为O(n)的最优解法还是需要仔细推敲下的。
例如有数组 int A[5] = {-1, 2, 3, -4, 2};
符合条件的子数组为 2,3 即答案为 5;
再明确一下题意
1.子数组必须是连续的。
2.不需要返回子数组的具体位置。
3.数组中包含:正整数,零,负整数。
例如
数组: {1, -2, 3, 5, -3, 2} 返回值为 8
数组: {0, -2, 3, 5, -1, 2} 返回值为 9
数组: {-9, -2, -3, -5, -6} 返回值为 -2 注意子数组不能为空
首先我们看看最直接的穷举法
intMaxSubString(int* A, intn)
{
intmax = min; //初始值为负无穷大
intsum;
for(inti = 0; i < n; i++)
{
sum = 0;
for(intj = i; j < n; j++)
{
sum += A[j];
if(sum > max)
max = sum;
}
}
returnmax;
}
这种方法最直接,当也是最耗时的,他的时间复杂度为O(n^2);
问题分析
可以优化吗?答案是肯定的,可以考虑数组的第一个元素,以及最大的一段数组(A[i], ..., A[j]),和A[0]的关系,有一下几种情况:
1. 当0 = i = j 时,元素A[0]本身构成和最大的一段;
2. 当0 = i < j 时,和最大的一段以A[0]开始;
3. 当0 < i 时, 元素A[0]和最大的一段没有关系。
从上面3中情况可以看出。
我们试着再观察这个数组的特点,一个元素一个元素的看。
根据A[0]是否在这个满足最大和的子数组中,我们可以分为两种情况。
1. 在。那么可以从A[0]开始求(比较容易)。
2. 不在。那么这种情况,又可以继续分为两种情况:A[1]在不在这个满足最大和的子数组中。
从这里我们可以观察出一种递归的特点,可以把一个规模为N的问题转化为规模为N-1的问题。所以这个从A[0]到A[n-1]的最大和子数组问题分解成:
1. 所求子数组中包含A[0]。如果不包含A[1],则A[0]自己满足条件,此时Max(A[0]……A[n-1])=A[0]。如果包含A[1],则Max(A[0]……A[n-1])=A[0]+Max(A[1]……A[n-1])。
2. 所求子数组中不包含A[0]。Max(A[0]……A[n-1])=Max(A[1]……A[n-1])。
最终结果取以上三者的最大值即可,即Max(A[0]……A[n-1])=max( A[0], A[0]+Max(A[1]……A[n-1]), Max(A[1]……A[n-1]))。
这个的复杂度为线性:因为只要把数组遍历一遍即可。
设sum[i] 为前i个元素中,包含第i个元素且到第i个元素的连续的最大子数组,(这个子数组不一定是从A[0]开始的,当sum[i]的值小于0的时候,而A[i+1]>0的时候就会新选择数组的起点,或者sum[i]<0,A[i+1]<0,且A[i+1]>sum[i]+A[i+1],换句话说如果sum[i]是正数,就不会新选择一个数组起点而都是累加进去),result 为已找到的子数组中和最大的。对第i+1个元素有两种选择:做为新子数组的第一个元素、放入前面找到的子数组。
sum[i+1] = max(a[i+1], sum[i] + a[i+1])
result = max(result, sum[i])
解决方案
intMaxSubString(int* A, intn)
{
intStart = A[n - 1];
intAll = A[n - 1];
for(inti = n - 2; i >= 0; i--) //
{
Start = max( A[i], A[i] + Start);//确定第i个元素,要么最大和只包括A[i]自己(之前的序列和是负的了),要么就是之前的序列连上A[i]
All = max(Start, All);
}
returnAll[0]; //All[0] 中存放结果
}
我们通过动规算法解决该问题不仅效率很高(时间复杂度为O(n)),而且极其简便。
01背包问题
题目
这题非常有名,只要是计算机专业的应该都有听说过。有N件物品和一个容量为V的背包。第i件物品的体积是c[i],价值是v[i]。求解将哪些物品装入背包可使价值总和最大。
我们把题目具体下, 有5个商品,背包的体积为10,他们的体积为 c[5] = {3,5,2,7,4}; 价值为v[5] = {2,4,1,6,5};
问题分析
这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。可以将背包问题的求解看作是进行一系列的决策过程,即决定哪些物品应该放入背包,哪些不放入背包。
如果一个问题的最优解包含了物品n,即Xn = 1,那么其余X1, X2, .....,Xn-1 一定构成子问题1,2,.....,n-1在容量C - cn时的最优解。如果这个最优解不包含物品n,即Xn = 0;
那么其余 X1, X2.....Xn-1一定构成了子问题 1,2,....n-1在容量C时的最优解。//请各位仔细品味这几句话
根据以上分析最优解的结构递归定义问题的最优解 f[i][v] = max{ f[i-1][v] , f[i-1][v - c[i]] + v[i]}
解决方案
#include<iostream>
#define max(a,b) ((a) > (b) ? a : b)
intc[5] = {3,5,2,7,4};
intv[5] = {2,4,1,6,5};
intf[6][10] = {0};
//f[i][v] = max{ f[i-1][v] , f[i-1][v - c[i]] + w[i]}
intmain()
{
for(inti = 1; i < 6; i++)
for(intj = 1; j < 10 ;j++)
{
if(c[i] > j)//如果背包的容量,放不下c[i],则不选c[i]
f[i][j] = f[i-1][j];
else
{
f[i][j] = max(f[i-1][j], f[i-1][j - c[i]] + v[i]);//转移方程式
}
}
std::cout<<f[5][9];
return0;
}
01背包问题是最基本的动态规划问题,也是最经典,最易懂的。所以请读者仔细推敲这段代码。它包含了背包问题中设计状态、方程的最基本思想。
矩阵连乘问题
题目
给定n个矩阵{A1,A2,...,An},其中Ai与Ai+1是可乘的,i = 1,2, ...n-1。考虑这n个矩阵的乘积。由于竞争乘法满足结合律,故计算矩阵的连乘有许多不同的计算次序。
这种计算次序可以用加括号的方式确定。若一个矩阵连乘的计算次序完全确定,这是就说该连乘已完全加括号。
例如,矩阵连乘A1 *A2 *A3 *A4 可以有5种完全加括号的方式:(A1 *(A2 *(A3 *A4 ))), (A1 *((A2 *A3) *A4)),((A1 *A2 )*(A3 *A4)),
(((A1 *A2 )*A3 )*A4)。每种加括号的方式确定了一个计算的次序。不同的计算次序与矩阵连乘的计算量有密切的关系。关于矩阵如何相乘这里我就不赘述了请看about matrix。
考虑3个矩阵{A1,A2,A3}连乘的例子,假设这3个矩阵的维数分别为 10×100, 100×5, 5×50。若按照((A1*A2)*A3)计算,则计算次数为10×100×5 + 10×5×50 = 7500
若按(A1*(A2*A3))计算,则计算次数为 100×5×50 + 10×100×50 = 75000。第1种方法的计算次数是后者的10倍!由此可以看出,不同的加括号方式确定不同的计算次序对
矩阵乘法的运算量影响是巨大的。
矩阵连乘为题定义如下:给定n个矩阵{A1,A2,...,An},矩阵A1的维数为pi-1×pi, i = 1,2, ..., n,如何给矩阵连乘A1*A2*....*An完全加上括号使用矩阵乘法中计算次数最少。
问题分析
若用穷举法,能够证明需要指数时间来求解。但是时间代价高昂。现在考虑用动态规划来求解连乘问题。
为方便起见用Ai...j表示矩阵乘法Ai*Ai+1*....Aj的结果。其中i<j。那么Ai*Ai+1*.....Aj一定在Ak与Ak+1之间被分裂。i <= k < j。问题Ai*Ai+1 ... Aj完全加括号的开销等于计算矩阵
Ai...k 与计算 Ak+1...j的开销,再加上他们的结果相乘的开销。问题的最优子结构可以描述如下:假定问题Ai*Ai+1*...Aj被完全加括号的最优方式是在Ak与Ak+1之间被分裂,那么分裂
之后,最优解Ai*Ai+1*....Aj中的子链Ai*Ai+1....Ak一定是问题Ai*Ai+1*...*Ak的最优加括号方式。同样,最优解Ak+1*Ak+2*...Aj的子链一定是问题Ak+1*Ak+2*...Aj最优加括号方式。
根据上面分析,设m[i,j]表示计算Ai...j所需的最小计算次数 m[i,j] = min{m[i,k]+m[k+1,j]+pi-1pKpj }
解决方案
#include<iostream>
voidmain() { intm[8][8], min; intr[8] = {10, 20, 50, 1, 100, 4, 20, 2}; /* 矩阵维数 */ /* 初始化 */ memset(m,0,sizeof(m)); /* 每此增量加一 */ for(intl = 1; l < 7; l++) { /* 对于差值为 l 的两个元素 */ for(inti = 1; i <= 7 - l; i++) { j = i + l; /* 求其最小组合方式 */ min = m[i][i] + m[i+1][j] + r[i-1] * r[i] * r[j]; middle[i][j] = i; for(intk = i + 1; k < j; k++) { if(min > m[i][k] + m[k+1][j] + r[i-1] * r[k] * r[j]) { min = m[i][k] + m[k+1][j] + r[i-1] *r[k]* r[j]; middle[i][j] = k; } } m[i][j] = min; } } std::cout<<m[1][N]; } |
由以上代码可以很容易看出算法的时间复杂度为O(n^3)。即便如此也比穷举法的指数级时间复杂度快。
尾声
动态规划绝对不是一两篇文章可以讲清楚的。当然也不是通过一两道题目可以完全学会。学习的关键是用动规的思想去想问题,去设计状态转移方程式。
动态规划还有很多变形,如状态压缩,树形等等。这些题目虽然很难,但是工作学习之余,一边听歌,一边推敲。也是人生一大快事
相关推荐
代码 随机动态规划的实例的matlab代码代码 随机动态规划的实例的matlab代码代码 随机动态规划的实例的matlab代码代码 随机动态规划的实例的matlab代码代码 随机动态规划的实例的matlab代码代码 随机动态规划的实例的...
动态规划是求解最优化问题的一种方法;动态规划虽然空间复杂度一般较大,但时间效率可观。但是,动态规划在求解中也会存在一些不必要、或者重复求解的子问题,这时就需要进行进一步优化。 在NOI及省选赛场上,一般...
【基于LINGO的优化问题动态规划法求解】 在运筹优化领域,LINGO是一款强大的数学建模软件,尤其适用于解决各种线性、非线性以及动态规划问题。不同于传统方法,LINGO甚至可以在没有明确目标函数的情况下解决动态...
本实验报告主要探讨了使用动态规划算法解决计算二项式系数的问题。实验者刘春云,专业为软件工程,通过这个实验学习并应用了动态规划这一核心的计算机科学概念。实验指导教师为赵晓平,实验时间为2012年2月21日。 *...
动态规划算法经典题目分析 动态规划是一种非常经典的算法思想,解决的问题领域非常广泛。动态规划的基本思想是将一个复杂的问题分解成多个小问题,通过解决这些小问题来解决整个问题。今天,我们将要探讨动态规划的...
动态规划是信息学竞赛中的常见算法,本文的主要内容就是分析 它的特点。 文章的第一部分首先探究了动态规划的本质,因为动态规划的特 点是由它的本质所决定的。第二部分从动态规划的设计和实现这两个 角度分析了动态...
动态规划是一种重要的算法思想,广泛应用于计算机科学,特别是在解决最优化问题时,如图论、组合优化、机器学习和自然语言处理等领域。在ACM(国际大学生程序设计竞赛)中,动态规划也是常考的题型,因为它能够帮助...
会议安排(贪心算法和动态规划) 会议安排问题是计算机科学中的一种经典问题,目的是在一系列活动中选择尽可能多的活动,使得每个活动的结束时间不早于下一个活动的开始时间。这个问题可以使用贪心算法和动态规划两...
贪心算法、分治算法和动态规划的区别 贪心算法、分治算法和动态规划是三种常用的算法设计策略,每种算法都有其特点和应用场景。下面我们将对这三种算法进行详细的比较和分析。 分治算法 分治算法是一种将原问题...
贪心算法、动态规划和分治法的区别 贪心算法是局部最优解的算法,它通过从上往下,从顶部一步一步最优,得到最后的结果。贪心算法顾名思义,就是做出在当前看来是最好的结果,它不从整体上加以考虑,也就是局部最优...
动态规划是一种解决问题的有效方法,尤其在处理具有重叠子问题和最优子结构的复杂问题时。旅行商问题(Traveling Salesman Problem, TSP)是一个经典的组合优化问题,它的目标是找到一个城市的最短可能路线,使得...
动态规划(Dynamic Programming,简称DP)是一种用于解决最优化问题的算法思想,它通过将大问题分解为相互重叠的子问题,并存储子问题的解,以避免重复计算,从而达到高效求解的目的。DP的核心在于它能够识别并利用...
从给定的文件标题“算法动态规划总结(拓展篇)”和描述“算法动态规划拓展总结,内含详细解说和代码”中,我们可以提炼出一系列关于动态规划算法的知识点,这些知识点涵盖了动态规划的多种应用及其优化技术。...
"动态规划C语言矩阵连乘" 动态规划是一种非常重要的算法思想,它可以解决很多 Optimization 问题。在这个资源中,我们将学习如何使用动态规划来解决矩阵连乘问题。 动态规划的基本思想是将待解决的问题分解成若干...
标题中的“dynprogs_MATLAB动态规划函数及测试程序_多阶段决策_多阶段规划_together1rz_”表明这是一个关于使用MATLAB实现动态规划算法的资源包,主要用于解决涉及多阶段决策和规划的问题。动态规划是一种在数学、...
动态规划增量动态规划水库优化调度程序代码 动态规划是一种常用的优化算法,它可以解决很多复杂的优化问题。增量动态规划是动态规划的一种变体,它可以更好地解决一些特殊的优化问题。在水库优化调度中,动态规划和...
动态规划(Dynamic Programming,简称DP)是解决复杂问题的有效算法设计方法,尤其在计算机科学和IT领域中占有重要地位。它通过将一个大问题分解为若干个子问题,并利用子问题的解来构建原问题的解,从而避免了重复...
本篇文章将深入探讨如何运用LINGO来解决动态规划问题,通过具体的案例分析,我们将了解LINGO在动态规划中的应用方法和步骤。 ### 动态规划与LINGO 动态规划是一种用于解决多阶段决策过程中的最优化问题的方法,其...