动态规划算法解决最优路径规划

m排n列的柱桩，每个柱桩上预先放好价值不一样的宝石。现在有位杂技演员从第一排的第1号柱桩开始跳跃，每次都必须跳到下一排的柱桩上，且每次跳跃最多只能向左或向右移动一个桩子。也就是说如果现在杂技演员站在第j号桩上，那么他可跳到下一排的第j号桩上，也可跳到下一排的第j-1 (if j>1)或者 j+1 (if j<n) 号桩上，并得到桩上的宝石。计算出一条最佳的跳跃顺序，使杂技演员获得的宝石的总价值最大。宝石价值和最优跳跃路径都保存在文件中。

// algorithm.cpp : 定义控制台应用程序的入口点。
//

#include “stdafx.h“
#include
#include
#include
#include
using namespace std;

//本函数功能为找出最优路径并输出到指定路径文件中
void diamond（int **aint m int n）
{   int b;

  //初始化一个全为0的数组d，用来存放最优路径中杂技演员处在每一行的列号：d[i][j]表示当小丑处在第i行第j个树桩上时，下一步跳上的树桩的列号（行号为i+1）
	int **d = new int*[m];  
    for（int i=0; i        d[i] = new int[n];
	for（int i=0;i		for（int j=0;j			d[i][j]=0;
	

	for（int i=1;i	{
   //考虑边界情况：当处在第0列时，下一步可能跳上的只可能是第0列和第1列，比较第m-i行这两列的值的大小并把较大者与a[m-i-1][0]上的数值相加存放在a[m-i-1][0]中
		if（a[m-i][0]>=a[m-i][1]）{            
			a[m-i-1][0]=a[m-i][0]+a[m-i-1][0];
			d[m-i-1][0]=0;
		}
		else{
		    a[m-i-1][0]=a[m-i][1]+a[m-i-1][0];
			d[m-i-1][0]=1;
		}


		if（m-i			for（int j=2;j				if（a[m-i][j-2]>=a[m-i][j-1]&&a[m-i][j-2]>=a[m-i][j]）{   //若第m-i行的第j-2个树桩上的钻石价值大于第j-1和第j个树桩上的钻石价值（连续的三个树桩）..
				  b=a[m-i][j-2];                                        //..就取第j-2个树桩..
				  d[m-i-1][j-1]=j-2;                                     //..将树桩的位置存放到数组d[m-i-1][j-1]中表示当小丑处在第m-i-1行第j-1个树桩上时，下一步跳上的树桩的列数，以下类似
				}
				else if（a[m-i][j-1]>=a[m-i][j-2]&&a[m-i][j-1]>=a[m-i][j]）{
				  b=a[m-i][j-1];
				  d[m-i-1][j-1]=j-1;
				}
				else{
				   b=a[m-i][j];
				  d[m-i-1][j-1]=j;
				} 
			    a[m-i-1][j-1]=b+a[m-i-1][j-1];
			}
		}
		else{       //与上方的 if（m-i=n，行数大于列数的情况
		//由于行数大于列数，此时除了考虑第0列的边界情况，还要考虑最后一列的边界情况.
		//处在第n-1列时，下一步可能跳上的只可能是第n-1列和第n列，比较第m-i行这两列的值的大小并把较大者与a[m-i-1][n-1]上的数值相加存放在a[m-i-1][n-1]中
			if（a[m-i][n-2]>=a[m-i][n-1]）{    
			   a[m-i-1][n-1]=a[m-i][n-2]+a[m-i-1][n-1];
			   d[m-i-1][n-1]=n-2;
			}
			else{
			    a[m-i-1][n-1]=a[m-i][n-1]+a[m-i-1][n-1];
			    d[m-i-1][n-1]=n-1;
			}

			//以下步骤同行数不大于列数的情况
			for（int j=2;j			   if（a[m-i][j-2]>=a[m-i][j-1]&&a[m-i][j-2]>=a[m-i][j]）{
				  b=a[m-i][j-2];
				  d[m-i-1][j-1]=j-2;
				}
				else if（a[m-i][j-1]>=a[m-i][j-2]&&a[m-i][j-1]>=a[m-i][j]）{
				  b=a[m-i][j-1];
				  d[m-i-1][j-1]=j-1;
				}
				else{
				   b=a[m-i][j];
				  d[m-i-1][j-1]=j;
				} 
			    a[m-i-1][j-1]=b+a[m-i-1][j-1];	
		    }  
		}
	}

	int *e = new int[m];  
	for（int i=0;i			e[i]=0;

	
	ofstream outfile;
	outfile.open（“..\\output.txt“）;  //打开输出文件

	outfile<	for（int i=1;i		e[i]=d[i-1][e[i-1]];
		outfile<	}

	cout<	outfile.close（）;
	
}

void main（）
{
 int data;
 int i=0j=0;
           
 fstream infile;
 infile.open（“..\\test.txt“ios::in）;  //打开源文件

 if（!infile）
 {
  cerr<<“File could not open.“;
  return;
 }                             

 int mn;
 infile>>data;    //读入行数
 m=data;
 infile>>data;   //读入列数
 n=data;


 //为原始二维数组a开辟空间
 int **a = new int*[m];  
 for（int i=0; i   a[i] 

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2013-06-05 20:23  algorithm\
     目录           0  2013-06-04 21:30  algorithm\algorithm\
     文件     9523200  2013-06-05 20:23  algorithm\algorithm.sdf
     文件         894  2013-05-22 14:43  algorithm\algorithm.sln
     文件       10752  2013-06-05 20:23  algorithm\algorithm.suo
     文件        3896  2013-06-04 21:32  algorithm\algorithm\algorithm.cpp
     文件        4403  2013-06-04 21:07  algorithm\algorithm\algorithm.vcxproj
     文件        1313  2013-05-22 14:43  algorithm\algorithm\algorithm.vcxproj.filters
     文件         143  2013-05-22 14:43  algorithm\algorithm\algorithm.vcxproj.user
     目录           0  2013-08-20 21:22  algorithm\algorithm\Debug\
     文件        1567  2013-05-22 14:43  algorithm\algorithm\ReadMe.txt
     文件         214  2013-05-22 14:43  algorithm\algorithm\stdafx.cpp
     文件         233  2013-05-22 14:43  algorithm\algorithm\stdafx.h
     文件         236  2013-05-22 14:43  algorithm\algorithm\targetver.h
     文件        1539  2013-05-28 22:06  algorithm\algorithm\test.txt
     目录           0  2013-06-04 21:32  algorithm\Debug\
     文件      684544  2013-06-04 21:31  algorithm\Debug\algorithm.exe
     文件     1701256  2013-06-04 21:31  algorithm\Debug\algorithm.ilk
     文件     2935808  2013-06-04 21:31  algorithm\Debug\algorithm.pdb
     文件      955866  2013-06-04 21:32  algorithm\Debug\Debug.rar
     目录           0  2013-06-05 19:39  algorithm\ipch\
     目录           0  2013-06-05 19:39  algorithm\ipch\algorithm-894a63aa\
     文件     2359296  2013-06-05 19:39  algorithm\ipch\algorithm-894a63aa\algorithm-915631f3.ipch
     文件         557  2013-06-04 21:32  algorithm\output.txt
     文件        1539  2013-05-28 22:06  algorithm\test.txt