汽车加油问题 动态规划

给定一个N*N 的方形网格，设其左上角为起点◎，坐标为（1，1），X 轴向右为正，Y轴向下为正，每个方格边长为1，如图所示。一辆汽车从起点◎出发驶向右下角终点▲，其坐标为（N，N）。在若干个网格交叉点处，设置了油库，可供汽车在行驶途中加油。汽车在行驶过程中应遵守如下规则： 　　　(1)汽车只能沿网格边行驶，装满油后能行驶K 条网格边。出发时汽车已装满油，在起点与终点处不设油库。 　　　(2)汽车经过一条网格边时，若其X 坐标或Y 坐标减小，则应付费用B，否则免付费用。 　　　(3)汽车在行驶过程中遇油库则应加满油并付加油费用A。 　　　(4)在需要时可在网格点处增设油库，并付增设油库费用C（不含加油费用A）。 　　　(5)(1)～(4)中的各数N、K、A、B、C均为正整数，且满足约束：2 ≤ N ≤100，2 ≤ K ≤10。设计一个算法，求出汽车从起点出发到达终点的一条所付费用最少的行驶路线。

#include
#include


void main（）
{
	int ijkpqxy;
	int NKABC;
	int map[81][81];//记录各个点的信息
	int cost[81][81][10];
	int min;
	int s[4][3];//4种行走方式
	FILE *fp;
	//从输入文件中读数据
	fp=fopen（“input.txt““rt“）;
	fscanf（fp“%d%d%d%d%d“&N&K&A&B&C）;
	for（i=1;i<=N;i++）
		for（j=1;j<=N;j++）
			fscanf（fp“%d“&map[i][j]）;
	fclose（fp）;
	
	//初始化行走方式的数组
	s[0][0]=-1;
	s[0][1]=0;
	s[0][2]=0;

	s[1][0]=0;
	s[1][1]=-1;
	s[1][2]=0;
	
	s[2][0]=1;
	s[2][1]=0;
	s[2][2]=B;
	
	s[3][0]=0;
	s[3][1]=1;
	s[3][2]=B;
	
	for（i=1;i<=N;i++）
		for（j=1;j<=N;j++）
			for（k=0;k<=K+1;k++） //注意这里！！！！
				cost[i][j][k]=10000;
	//走到11点的费用为0
	for（k=0;k<=K;k++）
				cost[1][1][k]=0;		
	y=1;
 
	while（y!=0）//修改的行数，当y等于0时说明所有数据为最优数据，跳出循环
	{
		//printf（“%d\n“y）;
		y=0;
		for（i=1;i<=N;i++）
		{
			for（j=1;j<=N;j++）
			{
				if（i!=1||j!=1） //ij同时为0时跳到下一次循环
				{
					for（p=0;p<=K;p++）//剩余的油量
					
					{
						min=10000;
						for（q=0;q<4;q++）//4种走法
						{
							if（（i==1&&q==0）||（j==1&&q==1）||（i==N&&q==2）||（j==N&&q==3））//边界情况
								continue;
							if（cost[i+s[q][0]][j+s[q][1]][p+1]+s[q][2]								min=cost[i+s[q][0]][j+s[q][1]][p+1]+s[q][2];
						}

						if（min<10000）//说明有路可以走过去
						{
							if（cost[i][j][p]>min+A*map[i][j]） //花费等于min+A*map[i][j]是合理情况，不合理情况时y++ 用来做标记
								y++;
							
							cost[i][j][p]=min;
							if（map[i][j]==1）
							{
								cost[i][j][0]+=A;
								for（x=1;x<=K;x++）
									cost[i][j][x]=cost[i][j][0];
								break;
							} 
						}
						else //没有路可以过去
						{
							cost[i][j][p]=cost[i][j][0]+C+A;
							for（x=p+1;x<=K;x++）
									cost[i][j][x]=cost[i][j][p];
								break;
						}
					}
				}
			}
		}
	}
	fp=fopen（“output.txt““w“）;
	fprintf（fp“%d\n“cost[N][N][0]）;
	fclose（fp）;
	system（“pause“）;
	
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       1992  2013-04-08 23:42  汽车加油问题\3-7.c

     文件       3365  2013-04-04 21:31  汽车加油问题\3-7.dsp

     文件        514  2013-04-05 00:42  汽车加油问题\3-7.dsw

     文件      41984  2013-04-08 23:42  汽车加油问题\3-7.ncb

     文件      48640  2013-04-08 23:42  汽车加油问题\3-7.opt

     文件        731  2013-04-08 23:40  汽车加油问题\3-7.plg

     文件     200792  2013-04-08 23:40  汽车加油问题\Debug\3-7.exe

     文件     213956  2013-04-08 23:40  汽车加油问题\Debug\3-7.ilk

     文件       5200  2013-04-08 23:40  汽车加油问题\Debug\3-7.obj

     文件     184616  2013-04-08 23:40  汽车加油问题\Debug\3-7.pch

     文件     525312  2013-04-08 23:40  汽车加油问题\Debug\3-7.pdb

     文件      33792  2013-04-08 23:40  汽车加油问题\Debug\vc60.idb

     文件      53248  2013-04-08 23:40  汽车加油问题\Debug\vc60.pdb

     文件        116  2013-04-01 07:42  汽车加油问题\input.txt

     文件          4  2013-04-08 23:40  汽车加油问题\output.txt

     文件      56832  2013-04-08 23:38  算法实现题 汽车加油行驶问题.doc

     目录          0  2013-04-08 23:40  汽车加油问题\Debug

     目录          0  2013-04-08 23:42  汽车加油问题

----------- ---------  ---------- -----  ----

              1371094                    18