算法分析⼤作业动态规划⽅法解乘法表问题和汽车加油⾏驶问题#精选.
算法分析⼤作业
动态规划⽅法解
乘法表问题和汽车加油⾏驶问题⽬录
1.动态规划解乘法表问题
1.1问题描述------
1.2算法设计思想------
1.3设计⽅法------
1.4源代码------
1.5最终结果------
2.动态规划解汽车加油⾏驶问题
2.1问题描述------
2.2算法设计思想------
2.3设计⽅法------
2.4源代码------
2.5最终结果------
3.总结
1.动态规划解决乘法表问题
1.1问题描述
定义于字母表∑{a,b,c)上的乘法表如表所⽰：
依此乘法表，对任⼀定义于∑上的字符串，适当加括号表达式后得到⼀个表达式。
例如，对于字符串x=bbbba，它的⼀个加括号表达式为(b(bb))(ba)。依乘法表，该表达式的值为a。
试设计⼀个动态规划算法，对任⼀定义于∑上的字符串x=x1x2…xn，计算有多少种不同的加括号⽅式，使由x导出的加括号表达式的值为a。
1.2算法设计思想
设常量a,b,c 分别为 1, 2 ,3 。n 为字符串的长度。
设字符串的第 i 到第 j 位乘积为 a 的加括号法有result[i][j][a] 种，
字符串的第 i 到第 j 位乘积为 b 的加括号法有result[i][j][b] 种,
字符串的第 i 到第 j 位乘积为 c 的加括号法有 result[i][j][c] 种。
则原问题的解是：result[i][n][a] 。
设 k 为 i 到 j 中的某⼀个字符，则对于 k 从 i 到 j ：result[i][j][a] += result[i][k][a] * result[k + 1][j][c] +
result[i][k][b] * result[k + 1][j][c] + result[i][k][c] * result[k + 1][j][a];
result[i][j][b] += result[i][k][a] * result[k + 1][j][a] +
result[i][k][a] * result[k + 1][j][b] + result[i][k][b] * result[k + 1][j][b];
result[i][j][c] += result[i][k][b] * result[k + 1][j][a] +
result[i][k][c] * result[k + 1][j][b] + result[i][k][c] * result[k + 1][j][c];
输⼊：输⼊⼀个以a,b,c组成的任意⼀个字符串。
输出：计算出的加括号⽅式数。
1.3设计⽅法
乘法表问题直观理解就是通过加括号使得最终运算结果为a，该问题与矩阵连乘问题类似，矩阵连乘是每⼀次加括号选择运算量最⼩的，写成数学表达式有：
⽽乘法表问题则是计算所有加括号运算结果为a的情况数，并不要求输出加括号⽅式。那么可以从乘法的最⼩单元两个符号相乘的所有可能开始，接着在两个符号相乘的基础上计算三个符号相乘的所有可能。直到计算N长度的符号1-N的所有可能。可以定义⼀个三维数组a[n][n][3],n为输⼊字符串的长度，a[i][j][0]为从字符串中第i个元素到第j个元素的⼦串表达式值为a的加括号⽅式数，a[i][j][1]为从字符串中第i个元素到第j个元素的⼦串表达式值为b的加括号⽅式数，a[i][j][2]为从字符串中第i个元素到第j 个元素的⼦串表达式值为c的加括号⽅式数。
由乘法表的定义则可知啊a[i][j][0]=（对k求和，k从i到j-1）a[i][k]
[0]*a[i][k+1][2]+a[i][k][1]*a[i][k+1][2]+a[i][k][2]*a[i][k+1]
[1];
同理可得到a[i][j][1]和a[i][j][2]。
同时由上⾯的表达式可知，要计算a[i][j][]，需先计算a[i][k][]和a[i][k
+1][]，这⾥k从i到j-1，故a[i][j][]可采取如下的计算次序
1.4源代码
#include "iostream"
#include "algorithm"
#include "fstream"
using namespace std;
/*
f[i][j][0] 表⽰在ch[i]~ch[j]之间以某种⽅式加括号后，结果为a f[i][j][1] 表⽰在ch[i]~ch[j]之间以某种⽅式加括号后，结果为b f[i][j][2]表⽰在ch[i]~ch[j]之间以某种⽅式加括号后，结果为c
a = a*c || b*c || c*a
b = a*a || a*b || b*b
c = b*a || c*b || c*c */
int f[50][50][3];
char chars[3] = {'a', 'b', 'c'};
int mul(int n, char ch[])
{
for(int i=0; i
for(int k=0; k<3; k++)
f[i][i][k] = (ch[i] == chars[k] ? 1: 0);
/*
a = a*c || b*c || c*a
b = a*a || a*b || b*b
c = b*a || c*b || c*c
*/
for(int r=1; r
for(i=0; i
{
int j = i + r; //区间右端点
for(int k=i; k
{
f[i][j][0] += f[i][k][0]*f[k+1][j][2] + f[i][k][1]*f[k+1][j][2] + f[i][k][2]*f[k+1][j][0]; f[i][j][1] += f[i][k][0]*f[k+1][j][0] + f[i][k][0]*f[k+1][j][1] + f[i][k][1]*f[k+1][j][1]; f[i][j][2] += f[i][k][1]*f[k+1][j][0] + f[i][k][2]*f[k+1][j][1] + f[i][k][2]*f[k+1][j][2]; }
}
return f[0][n-1][0];
}
int main()
{
ifstream fin("");
cout << "输⼊字符串：";
char ch[100];
fin >> ch; cout << ch;
int n = strlen(ch);
cout << "\n结果为a的加括号⽅式为：" << mul(n, ch) << endl;
fin.close();
return 0;
}
1.5最终结果
2.动态规划解决汽车加油⾏驶问题
2.1问题描述
给定⼀个N*N的⽅形⽹络，设其左上⾓为起点○，坐标为(1，1)，X轴向右为正，Y轴向下为正，每个⽅格边长为1。⼀辆汽车从起点○出发驶向右下⾓终点，其坐标为（M，N）。在若⼲⽹格交叉点处，设置了油库，可供汽车在⾏驶途中，可供汽车在⾏驶途中加油。汽车在⾏驶过程中应遵守如下规则：
（1）汽车只能沿⽹格边⾏驶，装满油后能⾏驶K条⽹格边。出发时汽车已装满油，在起点与终点处不设油库。
（2）当汽车⾏驶经过⼀条⽹格边时，若其X坐标或Y坐标减⼩，则应付费⽤B，否则免付费⽤。
（3）汽车在⾏驶过程中遇油库则应加满油并付加油费⽤A。
（4）在需要时可在⽹格点处增设油库，并付增设油库费⽤C（不含加油费A）。
（5）（1）~（4）中的各数N，K，A，B，C均为正整数。
2.2算法设计思想
这个题⽬，应该说是刚开始的时候被他给吓到了，只是想着如何去把所有的条件构造起来，然后使⽤⽹络流的⽅式来解决问题！但是，如果真的是很冷静下来好好地思考这道题⽬，就会发现如果没有那些限制条件，就是⼀个求解最长路的题⽬，这样就可以直接使⽤ＳＰＦＡ来解决这个问题！关键就是在于这个每次最多只能⾛Ｋ个⽹格边，这样就是限制了活动的范围，使得有的边⽆法扩展！因此可以考虑使⽤这个分层思想的最短路问题！就是通过将每⼀个点进⾏拆分，这样，就是相当于⼀种分类讨论的⽅式！⽽分类讨论
了之后，就知道哪些边是可以扩展的，哪些边是不能扩展的！关键点就是在于该如何选取变量来分层，
这就是因情况⽽异了！像这道题⽬之中，就是通过油量的多少来扩展边的！分层思想，说穿了其实就是相当于这个动态规划之中的增加变量的⽅式来确定状态⼀样，他们的实质其实都是⼀样的！2.3设计⽅法
采⽤的是动态规划的思想来解题,⽤备忘录的⽅法进⾏递归，递归的式⼦后⾯写出.
不能直接以汽车⾏驶的费⽤为⽬标来进⾏动态规划，因为最优⼦结构性质得不到证明.
所以必须把油量和费⽤⼀起考虑，作为动态规划的对象，此时就有了最优⼦结构性质.
最优⼦结构性质的证明
证明：假设路径M是从起点◎到终点▲的⼀条最⼩费⽤路径,P(x,y)是M 经过的⼀个点(⾮加油站)，且油量和费⽤为(g,c)，现假设有⼀条新路径Q从起点◎到点P(x,y)，使得其在P(x,y)点的油量和费⽤为(g,c')，其中c'备忘录递归
刚开始的时候为每个⽹格点P(x,y)建⽴⼀个记录，初始化时，为该记录存⼊⼀个特殊值W，表⽰汽车未⾏驶过.那么在汽车⾏驶过程
中，对每个待求的汽车最⼩费⽤值COST，先查看其相应的记录项C，如果存储的是初始值W，那么表⽰这个点P(x,y)是第⼀次遇到，此时计算出该点的最⼩费⽤值，并保存在其相应的记录项中，以备以后查
看.若记录项C中存储的不是初始值W，那么表⽰该问题已经求解过了，其相应的记录项中存储的就是该点的最⼩费⽤值COST，此时要取出记录项C的值跟最新的计算出的COST进⾏⽐较，取其最⼩的那个数存⼊到C中.依此建⽴记录项C的值，当程序递归完成时，我们也得到了汽车⾏驶到(n,n)的最⼩费⽤值COST.
2.4源代码
#include "iostream"
#include "algorithm"
#include "fstream"
using namespace std;
#define INF 10000
/*
f[i][j][0]表⽰汽车从⽹格点(1,1)⾏驶⾄⽹格点(i,j)所需的最少费⽤
f[i][j][1]表⽰汽车⾏驶⾄⽹格点(i,j)还能⾏驶的⽹格边数
s[i][0]表⽰x轴⽅向
s[i][1]表⽰y轴⽅向
s[i][2]表⽰⾏驶费⽤
f[i][j][0] = min{f[ i+s[k][0] ][ [j+s[k][1] ][0] + s[k][2]}
f[i][j][1] = f[ i+s[k][0] ][ [j+s[k][1] ][1] - 1;
f[1][1][0] = 0
f[1][1][1] = K
f[i][j][0] = f[i][j][0] + A , f[i][j][1] = K 如果(i, j)是油库
f[i][j][0] = f[i][j][0] + C + A, f[i][j][1] = K (i, j)不是油库，且f[i][j][1] = 0
*/
int N; //⽅形⽹络规模
int A; //汽车在⾏驶过程中遇到油库应加满油并付加油费A
int C; //在需要时可在⽹格点处增设油库，并付增设油库费⽤C（不含加油费A）
int B; //当汽车⾏驶经过⼀条⽹格边时，如果其x坐标或y坐标减少，应付费⽤B
int K; //装满油后，还能⾏驶K条边
int f[50][50][2];
int s[4][3] = {{-1,0,0},{0,-1,0},{1,0,B},{0,1,B}};
int a[50][50]; //⽅形⽹络
int dyna()
{字符串长度为0
int i, j, k;
for (i=1;i<=N;i++)
{
for (j=1;j<=N;j++)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。