赶紧，趁着还没睡觉，给我解释个问题。快来快来~~~~~~~~~
动态规划算法解决骑车加油行驶问题
给定一个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]} .
看看我的代码中，可能还有问题，先贴上去再说吧：
代码
- C/C++ code
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; }}
以上都是转自某人blog，以下是我的疑问了。
=================================================================
最优子结构 C(x,y,g)=min{C(x+s[i][0],y+s[i][1],0)+s[i][2]}
即前一步剩0油的最少费用+到走一步的费用才是符合最优的，感觉这个不处理一下没法写成DP算法。
我要求C(n,n,0),可是子问题里的g并不一定是0了。 这是个天大的问题。。
然后，我就看不懂这个算法具体实现的时候怎么处理的。
你看他初始化f[][]=10000 f1[][]=0 ，f[][]应该是记录费用的吧，可是我不知道它记录的是啥费用。
f1[][]应该是记录油量的吧，可是我不知道记录它干啥用。
int ftemp = f[x][y] + s[i][2];
int ftemp1 = f1[x][y] + s1[i][2];
这是干啥，一个10000+一个路径耗费，一个0+一个路径耗费，这算法到底干嘛呢。
这人是不是写错了啊，怎么写才能转换成可以DP的。高人指点！
[解决办法]
真难啊
[解决办法]
题目看着真复杂呀，LZ有原题的地址么？
[解决办法]
用一个f[i,j,l]的三维DP可以解，i,j是x,y坐标，l是剩余油量（这是最普通的方法了）。
实际上还有很大的可优化的空间，利用四边形不等式可知当,x >= x' y >= y'l >=l'时，
x,y,l是一组更好的解。
从0,0点开始递推，计算周围2个点的情况，再从这两个点推算其他的点（费用+B），碰到重复的点时，需要取多个分支的最小，碰到加油站时，需要+A，并灌满油箱，碰到没油的情况，需要建立加油站，+C，大概就这几种情况吧。
[解决办法]
算法问题，不会，帮顶·
http://topic.csdn.net/u/20100321/20/1e24f731-75d2-43e0-804b-fc8eba1bc3ad.html?seed=1878887270&r=64084724#r_64084724http://topic.csdn.net/u/20100321/20/1e24f731-75d2-43e0-804b-fc8eba1bc3ad.html?seed=1878887270&r=64084724#r_64084724
搭个车，求个高手付费一对一指导
[解决办法]
我不知道有没有经典的解决方法。
我的想法是你纵向优先的方式去求每个路径（记录路径方向）。
每个站点设4个属性：是否经过过；向上费用；向向下费用；向左费用；向右费用。
每经过一个站点，给这个点记录已经经过过，在任何一个站点优先计算没有经过过的相邻站点的费用，其次计算经过过但没计算到终点的费用。计算得到一条路径的终点后返回总费用，逐级累计出经过的各个站点到终点的方向和各方向费用。如果这个站点在某方向已经已经有到终点的费用，返回此费用，如果还没有，递归计算之。当一个站点4个方向的费用都算出来后，取最小费用和其开出方向作为此站点的费用及方向。
其中遇到油耗干的点就增加油库，但是临时增的油库只给本点为起点的路径计算加油，要区分原油库和临时设置的油库
[解决办法]
新手。。。 观摩+学习来了。。。。