赶紧，趁着还没睡觉，给我解释个问题。快来快来~~~~~~~~~
动态规划算法解决骑车加油行驶问题
给定一个N×N的正方形网格,设其左上角为起点◎,坐标为(1,1),X轴向右为正,Y轴向下为正,每个方格边长为1,如图所示.一辆汽车从起点◎出发驶向右下角终点▲,其坐标为(N,N).在若干个网格交叉点处,设置了油库,可供汽车在行驶途中加油.汽车在行驶过程中应遵守如下规则:
(1)汽车只能沿网格边行驶,装满油后能行驶K条网格边.出发时汽车已装满油,在起点与终点处不设油库.
(2)汽车经过一条网格边时,若其X坐标或Y坐标减小,则应付费用B,否则免付费用.
(3)汽车在行驶过程中遇油库则应加满油并付加油费用A.
(4)在需要时可在网格点处增设油库,并付增设油库费用C(不含加油费用A)
N,K,A,B,C均为正整数,且满足约束:2≤N≤100, 2≤K≤10
求出汽车从起点出发到达终点的最少费用.
示 例
数据输入:由文件input.txt提供输入数据.文件的第一行是N,K,A,B,C的值.第二行起是一个N*N 的0-1 方阵,每行N 个值,至N+1 行结束.方阵的第i 行第j 列处的值为1 表示在网格交叉点(i,j)处设置了一个油库,为0 时表示未设油库.各行相邻两个数以空格分隔.
输入文件示例 输出文件示例
input.txt output.txt
9 3 2 3 6 12
0 0 0 0 1 0 0 0 0
0 0 0 1 0 1 1 0 0
1 0 1 0 0 0 0 1 0
0 0 0 0 0 1 0 0 1
1 0 0 1 0 0 1 0 0
0 1 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0 1
1 0 0 1 0 0 0 1 0
0 1 0 0 0 0 0 0 0
解 题 思 路
采用的是动态规划的思想来解题,用备忘录的方法进行递归,递归的式子后面写出.
不能直接以汽车行驶的费用为目标来进行动态规划,因为最优子结构性质得不到证明.
所以必须把油量和费用一起考虑,作为动态规划的对象,此时就有了最优子结构性质.
最优子结构性质的证明
证明:假设路径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.
备忘录递归式
C(x,y,g)表示在(x,y)位置上,剩余油量为g时的所耗费用.
C(x,y,g)=min{C(x+s[i][0],y+s[i][1],0)+s[i][2]}.其中0≤i≤3.
用3维数组s={{-1,0,0},{0,-1,0},{1,0,B},{0,1,B}}表示汽车的行驶方向.
当行驶到油库时,要加满油,故有: C(x,y,g)= C(x,y,K)= C(x,y,g) + A.
当油用尽但还没到油库时,要建立油库,并且加油,故有: C(x,y,0)= C(x,y,K)= C(x,y,0) + C + A.
初始值与最优解
C(1,1,0)=0,C(1,1,1)=k;
C(1,1,k)=0;
用备忘录方法递归计算,c(n,n,0)为最优解.
当然，思路归思路，代码中可不能按思路这么走。因为你不可能实现C(x,y,g)=min{C(x+s[i][0],y+s[i][1],0)+s[i][2]} .
看看我的代码中，可能还有问题，先贴上去再说吧：
代码
class Min{ friend void FindMin(int x,int y) { for(int i=0;i<4;i++) { if(y == 1&&i == 0) { continue; } if(x == N&&i == 1) { continue; } if(y == N&&i == 2) { continue; } if(x == 1&&i == 3) { continue; } int ftemp = f[x][y] + s[i][2]; int ftemp1 = f1[x][y] + s1[i][2]; //如果此处是油库 if(Matrix[x+s[i][0]][y+s[i][0]] == 1) { //附加邮费 ftemp +=A; //装满油 ftemp1 = K; } else //如果不是油库 { if(f1[x+s1[i][0]][y+s1[i][1]] == 0) { ftemp +=A+C; ftemp1 = K; } } if(ftemp<f[x+s[i][0]][y+s1[i][1]]&&ftemp1<f1[x+s1[i][0]][y+s1[i][1]]) { f[x+s[i][0]][y+s1[i][1]] = ftemp; f1[x+s[i][0]][y+s1[i][1]] = ftemp1; FindMin(x+s[i][0],y+s[i][1]); } } }private: int /*N*N的方形网格*/N; int /*装满油后能走K条*/K; int /*附加油费*/A; int /*倒走一条网格应付B费*/B; int /*曾建油库*/C; int **Matrix/*矩阵*/; int f[100][100]; int f1[100][100]; int s[4][3] = {{-1,0,B},{1,0,0},{1,0,0},{-1,0,B}}; int s1[4][3] = {{-1,0,-1},{1,0,-1},{}};public: void MinInitialize(int aN,int aK,int aA,int aB,int aC,int **Matrix) { N = aN; K = aK; A = aA; B = aB; C = aC; Matrix = Matrix; for(int i = 1;i<=N;i++) { for(int j = 1;j<=N;j++) { f[i][j] = 10000;/*最大值*/ f1[i][j] = 0; } } f[1][1] = 0; f1[1][1] = K; }}