重庆大学算法导论跳桩得珠宝问题项目报告(包含报告及源代码).doc

重庆大学项目报告

项目题目： 跳桩得珠宝问题
学 院：
专业班级： 计科
年 级： 2011级
姓 名：
学 号：
完成时间： 2013 年 6 月 7 日
指导教师： 陈波

重庆大学教务处制

项目报告正文
一.问题描述

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

二.算法思想

问题抽象：

对于这个问题，可以抽象为：从顶部出发，在每一结点可以选择向左走，向下走或是向右走， 一直走到底层，要求找出一条路径，使路径上的值最大。

问题分析：
这道题如果用枚举法，在数塔层数稍大的情况下（如40），则需要列举出的路径条数将是一个非常庞大的数目。
如果用贪心法又往往得不到最优解。
在用动态规划考虑数塔问题时可以自顶向下的分析，自底向上的计算。于是在确定使用动态规划的情况下，对该问题进行分析。

算法思想：
从顶点出发时到底向左走，向下走还是向右走应取决于是从哪个方向走能取到最大值，
只要左中右三道路径上的最大值求出来了才能作出决策。同样的道理下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。 这样一层一层推下去，直到倒数第二层时就非常明了。所以实际求解时，可从底层开始，层层递进，最后得到最大值。
首先，我可以确定，对于矩阵可以用一个二维数组dp储存它，并且可以用（i,j）描述一个数字在矩阵中的位置。对于中间的一个点来说，想经过它则必须经过它的上方或左上或右上，也就是说经过这个点的数字和最大等于经过上方或左上方或右上方的所得的“最大和”中一个更大的加上这个点中的数字。显然这个定义满足最优子结构。

三.递推方程式

设计一个二维状态opt[i,j]表示走到第i行第j列时经过的数字的最大和。决策是opt[i-1,j] 或opt[i-1,j-1]或opt[i-1,j+1]中一个更大的加上（i,j）点的数字。
对于一个点只考虑上面或左上或右上即前一阶段，满足无后效性。
状态转移方程（顺推）：
opt[i-1,j]+dp[i,j] (j=1)
opt[i,j]= opt[i-1,j-1]+ dp[i,j] (j=max)
max{opt[i-1,j],opt[i-1,j-1]}+ dp[i,j] (1<j<max)
实现时可以将opt[i,j]的左右边界定义的大点，初始opt[i,j]=0，由于在j=1时opt[i-1,j-1]=0,opt[i-1,j]>=0所以方程也可以这样写：
opt[i,j]=max{opt[i-1,j],max（opt[i-1,j-1]，opt[i-1,j+1]）}+a[i,j]
同理j=i时方程也可以写成上面那样，所以方程综合为：
opt[i,j]=max{opt[i-1,j],max（opt[i-1,j-1]，opt[i-1,j+1]）}+a[i,j] (1<j<max)
显然答案是走到底后的一个最大值，即：
ans=max{opt[n,i]} (1<=i<=n)
其实从上往下走和从下往上走结果是一样的，但是如果从下往上走结果就是opt[1,1]省下求最大值了，所以方程进一步改动（逆推）：
opt[i,j]=max{opt[i+1,j],max（opt[i-1,j-1]，opt[i-1,j+1]）}+a[i,j]（0<j<=i）

四.最优子结构性质

对于中间的一个点来说，想经过它则必须经过它的上方或左上或右上，也就是说经过这个点的数字和最大等于经过上方或左上方或右上方的所得的“最大和”中一个更大的加上这个点中的数字。显然这个定义满足最优子结构。以此为递推关系。

五.程序结构的描述

此程序主要分为以下四个部分
文件读入(从文件中读取矩阵的值应存入二维数组中)
最大值计算(用递推式推出)
明确路径(用一个path数组记录下动态)
在文件中显示(读入文件)

最大值的计算主要用上述递推式，路径的求得是定义了一个二维数组path，用这个二维数组存取dp中相对应位置的路线动态，比如说在（i，j）点在接下来一行要向右，我们就将path[i][j]赋值为1，则循环时用i++；j+=path[i][j]，就将位置右移一个，同理可令向左为-1，向下为0.

for(int i = 0, j = 0; i<M; ++i)
{
file2<< "[" << i+1<< "," << j+1 << "]" << " -> ";
j += path[i][j];
}

六.计算复杂度分析
此实验中，作为基本操作的原操作是max（）；即比较函数，在循环中，进行了N^2次，而比较函数其运行时间为常数O（1），故计算最大值部分T（n）=O（n^2）；同理，在路径输出部分，关键代码是j+=path[i][j];其T（n）=O(n);该算法总的时间复杂度T（n）=O（n^2）。七.测试结果:
test.txt文件：

柱桩20排20列：

柱桩4排4列：

全部代码：
#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;
int const MAX =20;
int M,N,num=0;
int main()
{
int count=0;
fstream file1,file2;
file1.open("test.txt",ios::in);
if(!file1)
cout<<"input file not founded"<<endl;
cout<<" **************跳桩得珠宝****************"<<endl;
cout<<" *************1柱桩20排20列**************"<<endl;
cout<<" *************2自定义柱桩排列************"<<endl;
cout<<"请输入您的选择：";
cin>>num;
if(num==2){
cout<<"请输入排与列（排与列均小于20）："<<endl;
cin>>M>>N;
}
else{
if(num==1)
M=N=MAX;
else
cout<<"输入不符，重新启动！";
}
int dp[MAX][MAX] = {0};
int path[MAX][MAX] = {MAX};//描写路径的坐标
while(!file1.eof())//是否到文件结尾
{
for(int i=0;i<M;i++)

for(int j=0;j<N;j++)
{
file1>>dp[i][j];
count++;
}

if(count==M*N)
break;
}
file2.open("output.txt",ios::out);
if(!file2)
cout<<"output file not founded"<<endl;
for(int i=0;i<M;i++)
{
for(int j=0;j<N;j++)
{
file2<<dp[i][j];
file2<<",";
}
file2<<"\n";
}
file1.close();
for(int i=M - 2; i>=0; i--)
{
for(int j=0; j<=N-1; j++)
{
if(j==0)
{
dp[i][j] = max(dp[i + 1][j],dp[i+1][j+1]) + dp[i][j];
if (dp[i+1][j] > dp[i+1][j+1]) //正下方大
path[i][j] = 0; //选择正下方
else //右边大
path[i][j] =1; //选择右边
}

else
{
dp[i][j] = max(dp[i + 1][j-1], max(dp[i + 1][j],dp[i+1][j+1])) + dp[i][j];
if((dp[i+1][j-1] >=dp[i+1][j])&&(dp[i+1][j-1] >=dp[i+1][j+1]))
path[i][j] = -1;
else
if((dp[i+1][j] > dp[i+1][j-1])&&(dp[i+1][j] >=dp[i+1][j+1])) //正下方大
path[i][j] = 0; //选择正下方
else //右边大
path[i][j] = 1; //选择右边
}
}
}
file2<<dp[0][0]<<" (最大价值)"<< endl;
for(int i = 0, j = 0; i<M; ++i)

{
file2<<j+1 <<endl;
j += path[i][j];

}
return EXIT_SUCCESS;
}
参考资料：
Algorithm Design, Jon Kleiberg. Eva Tardos, Cornell University

9