动态规划实验报告

实验报告题目

实验一 动态规划

开课实验室：数学实验室 指导老师：韩逢庆 时间：2011.12 学院：理学院 专业：信息与计算科学 班级：2009级2班 姓名：古月 学号：09180230

一、 实验目的

1．加深学生对动态规划算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；

2．提高学生利用课堂所学知识解决实际问题的能力；

3．提高学生综合应用所学知识解决实际问题的能力。

二、 实验内容

题目见P102：3-3,3-12,3-15,3-19,3-21,3-23。

三、 实验要求

（1）动态规划法求解独立任务最优调度问题，三维01背包问题，游艇最少租金问题；

（2 ）再选择自己熟悉的其它方法求解本问题；

（3）上机实现所设计的所有算法；

四、 实验过程设计（算法设计过程）

（1） 独立任务最优调度问题

实验题目：

用2台处理机A和B处理n个作业。设第i个作业交给机器A处理需要时间ai。由机器B来处理，则需要时间bi。由于各作业的特点和机器的性能关系，很可能对于某些问题i，有aibi，而对于某些问题

j，ji,有ajbj。既不能将一个作业分开由两台机器处理，也没有一台机器能同时处理2个作业。设计一个动态规划算法，使得这两台及其处理完这n个作业的时间最短（从任何一台季芹开工到最后一台机器停工的总时间）。研究一个实例

(a1,a2,a3,a4,a5,a6)(2,5,7,10,5,2)； (b1,b2,b3,b4,b5,b6)(3,8,4,11,3,4)。 过程设计：

这个实验就是求解在一定任务的数量，和一定的工作机器下面求解用这些处理机完成所有这些任务最少的时间。在分析题目以后，认识到动态规划问题能够很好的解决它。采用自底向上的方式，首先我们可以选择两台处理机同时处理开动，完成最后一个任务。其实这时候只要选择处理机A或者处理机B两台处理机中完成的任务N时间较少的那一个。这里只需要一次比较，记录处理机A完成任务N的时间和处理机B完成任务N的时间中的较小的一个。在进行第二步的时候，把问题处理的个数有原来的第N个变成现在的第N个和第N-1个。然后分别比较两种情况，也就是处理机A处理任务N，同时并行处理机B处理任务N-1的时间，或者是处理机A处理任务N-1，同时并行处理机B处理任务N的时间，从中我们选择较小的一个记录为第二层处理的时间。然后以此类推，可以得到用动态规划算法处理这个问题的基本表达式为：

piak1k1,iak10j pijk]k1),jbk10minpijk||pijbk1

其中pijk的是从任务K到任务N最少完成时间，ak为处理机A完成第K个任务时间，bk为处理机B完成第K个任务需要时间。

在程序的执行过程中，只要调用一次pij1就可以算出这个问题的最优解。在执行过程中，选择的随机输入的形式，增强了文件的可移植性。

（2） 三维01背包问题

实验题目

给定n种物品和一背包，物品t的重量是w，体积是b，价值是v，背包的容量为C，容积为D，问：应该如何选择装入背包中的物品，使得装入背包中物品的总价值最大？在选择装入背包中的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品装入背包多次，也不能只装入部分的物品i。试设计一个解决此问题的动态规划算法，并分析算法的计算复杂性。

过程分析

此问题的形式描述为：给定C0,wi0,vi0,bi0,1in，要求找出N元0-1向量(x1,x2,,xn),xi{0,1}，使得wixiC，bixiD，而且使得

i1i1nn

vx达到最大。因此，0-1背包问题是一个特殊的整数规划问题。 ii

i1n

可以建立以下递归关系：

maxzvixi

i1

nwixiCi1nbixiD i1xk{0,1},iknn

的最优值为m(i,j,k)，即mi可乘重为k,可选择的(,j,k)是背包容量为j，

物品为i,i1,,n时的背包问题的最优值。由0-1背包问题的最有子结构性质，可以建立如下计算m(i,j,k)的递归式为：

vi),jwi,,kbikbimax(mi1jk,mi1jwi m(i,j,k)mi1jr,0jwi||0kbi

v,jwn&&kbn m(n,m,k)n

0

（3） 游艇最少租金问题

实验题目：

长江游艇俱乐部在长江上设置了n个游艇出租站1,2，…，n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j),1ijn，设计一个算法，计算出从游艇出租站1到游艇出租站n所需的最少租金。 过程分析

在这个题目中，首先我们想到的就是如何使得当游客从第一个游艇出租站到最后一个游艇出租站的总共所用的租金最少的问题。在这个问题总，采用动态规划自底向上的方式，不断的加入游艇出租站的个数，分别别算出此时的费用为 tempfipfpj，然后与当前的最少费用相比较，不断的更新fijtemp，这样既可求得最优解。 这里附上动态规划算法的核心算法为：

void dyna()

{

for(int k=2;k

for(int i=0;i

{

int j=i+k;

} } for(int p=i+1;ptemp) f[i][j]=temp; }

五、 实验结果分析

（1） 独立任务最优调度问题

（分析时空复杂性，设计测试用例及测试结果）

时间复杂性：

最好情况下，算法的时间复杂性为O(n2)。

最坏情况下，算法的时间复杂性为O(n2)。

空间复杂性分析：，算法的空间复杂性为O(n)

（2） 三维01背包问题

（分析时空复杂性，设计测试用例及测试结果）

时间复杂性：该算法的时间复杂性为O(nmj)

空间复杂性分析：该算法的空间复杂度为O(nm)

（3） 游艇的最少租金问题

（分析时空复杂性，设计测试用例及测试结果）

时间复杂性：该算法的时间复杂性为：O(n2)

空间复杂性分析：该算法的空间复杂性为：O(n)

六、 实验体会

通过本次实验加深了我对动态规划算法的理解。而且对动态规范编写代码解决一个实际问题有了进一步的认识。即当算法考虑的原问题的每一个子问题，算法都需要计算一个最优解。换句话说，所有算法生成的表项表示算法考虑的子问题的最优解。这时候用动态规范把每一个最优解求出来（利用递归公式），就能够保证最后求得的一定是最优解。而且动态规划有个特点，即它是由底向上，它实现起来就是利用循环，有时用到一层循环即可，有时要用到两层for循环即可以求解出问题。但是在设计程序的出口的时候，设计程序发生异常情况的时候，都应该编写出相应的边际条件然后给予说明，才能使得程序更加的完备。

在采用动态规划问题的时候，我们需要了解的核心问题就是找出问题的最优子结构，然后采用自底向上的方式构造出最优解。

七、 附录：（源代码）

（1）独立任务最优调度问题

具体算法实现如下：

#include

#include

//using namespace std;

int n,mn,opt;

int ***p;

int* a;

int* b;

void dyna()//动态规划法求解

{

int i,j,k;

for(i=0;i

for(j=0;j

for(k=1;k

{

if(i-a[k-1]>=0)

p[i][j][k]=p[i-a[k-1]][j][k-1];

if(j-b[k-1]>=0)

p[i][j][k]=(p[i][j][k]||p[i][j-b[k-1]][k-1]); }

for(i=0,opt=mn;i

for(j=0;j

if (p[i][j][n])

{

int temp = (i>j)?i:j;

if(temp

}

}

void main()

{

int m;

cout

cout

cout

a = new int[n];

b = new int[n];

for(int i=0;i

{

scanf(

if(a[i]>m) m = a[i];

}

for(i=0;i

{

scanf(

if(b[i]>m)m = b[i];

}

mn = m*n;

p = new int** [mn+1];//动态分配内存并为三维数组赋值 for(i=0;i

{

p[i] = new int*[mn+1];

for(int j=0;j

{

p[i][j] = new int[n+1];

for(int k=0;k

{

if(k==0) p[i][j][k]=1;

if(k!=0) p[i][j][k]=0;

}

}

}

dyna();

cout

}

（2）三维0-1背包问题

具体算法实现如下：

#include

#include

#include

int min(int a,int b)

{

}

int max(int a,int b) {

}

void main() {

int c,d,n,w[20],b[20],v[20],best,i,j,r,N,x[20]; cout

cout

} for(j=w[i];j

（3）游艇的最少租金问题

具体算法实现如下：

#include

#define N 200

int f[N][N];

int n;

void init()

{

int i,j;

for(i=0;i

for(j=0;j

f[i][j]=0;

cout

for(i=0;i

for(j=i+1;j

{

cout

}

}

void dyna()

{

for(int k=2;k

for(int i=0;i

{

int j=i+k;

for(int p=i+1;p

{

int temp=f[i][p]+f[p][j];

if(f[i][j]>temp)

f[i][j]=temp;

}

}

}

void main()

{

cout

cin>>n;

init();

dyna();

cout