实验二

西安邮电大学

（计算机学院）

课内实验报告

实验名称：动态规划

专业名称：软件工程

班级：01班

学生姓名：张世强

学号（8位）：04113021

指导教师：刘伟

实验日期：2013年10月23号

一. 实验目的及实验环境

1．加深学生对动态规划算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；2．提高学生利用课堂所学知识解决实际问题的能力；

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

二. 实验内容

1、用两台处理机A和B处理n个作业。设第i个作业交给机器A处理时所需要的时间是a[i]，若由机器B来处理，则所需要的时间是b[i]。由于各作业的特点和机器的性能关系，很可能对于某些i，有a[i]>=b[i]，而对于某些就j，j!=i,有a[i]

2、长江游艇俱乐部在长江上设置了n个游艇出租站1，2……n。游客可在游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金r（i，j）1<=i

三．方案设计

1、对于给定的2台处理机A和B处理n个作业，找出一个最优调度方案，使2台机器处理完这n个作业的时间最短。

2、对于给定的游艇出租站i到游艇出租站j之间的租金为r（i，j），1<=i

四．测试数据及运行结果

独立任务最优调度问题：

租用游艇问题：

时间复杂性：独立任务最优调度问题：O(n*Sum)

五．总结

对于算法来说，没有最好，只有更好，算法的结果不一定是最佳答案，但至少是最接近最佳答案的。在权衡算法时间复杂度和空间复杂度的情况下，找到一个在时间和空间都能接受的算法才是上上之策。

六．附录：源代码（电子版）

using System;

namespace zydd

{

class Program

{

static void DlrwZydd(int[] a, int[] b, int n, int[] least, string[] result)

{

for (int i = 0; i < n; i++)

{

least[i] = 99;

}

int aSum = 0, bSum = 0;

for (int i = 0; i < n; i++)

{

aSum += a[i];

bSum += b[i];

}

int Sum = 1 + Math.Min(aSum, bSum);

int[,] timeA = new int[n, Sum];

int[,] timeB = new int[n, Sum];

int[,] timeMax = new int[n, Sum];

char[,] who = new char[n, Sum];

char[] tempRlt = new char[n];

for (int i = 0; i <= a[0]; i++)

{

timeA[0, i] = i;

if (i < a[0])

{

timeB[0, i] = b[0];

who[0, i] = 'b';

}

else

{

timeB[0, i] = 0;

who[0, i] = 'a';

}

timeMax[0, i] = Math.Max(timeA[0, i], timeB[0, i]);

}

if (a[0] <= b[0])

{

least[0] = a[0];

tempRlt[0] = 'a';

}

else

{

least[0] = b[0];

tempRlt[0] = 'b';

}

result[0] = new String(tempRlt);

for (int k = 1; k < n; k++)

{

int tempSum = 0;

for (int temp = 0; temp <= k; temp++)

{

tempSum += a[temp];

}

for (int i = 0; i <= tempSum; i++)

{ timeA[k, i] = i;

if (i < a[k])

{

timeB[k, i] = timeB[k - 1, i] + b[k];

who[k, i] = 'b';

}

else

{

if ((timeB[k - 1, i] + b[k]) <= timeB[k - 1, i - a[k]])

{

timeB[k, i] = timeB[k - 1, i] + b[k];

who[k, i] = 'b';

}

else

{

timeB[k, i] = timeB[k - 1, i - a[k]];

who[k, i] = 'a';

}

}

timeMax[k, i] = Math.Max(timeA[k, i], timeB[k, i]);

}

for (int i = tempSum + 1; i < aSum; i++)

{

timeA[k, i] = tempSum;

timeB[k, i] = 0;

}

int flag = 0;

for (int i = 0; i <= tempSum; i++)

{

if (timeMax[k, i] > 0 && timeMax[k, i] < least[k])

{

least[k] = timeMax[k, i];

flag = i;

}

}

tempRlt[k] = who[k, flag];

for (int i = k; i > 0 && flag > 0; i--)

{

if (tempRlt[i] == 'a')

{

flag -= a[i];

tempRlt[i - 1] = who[i - 1, flag];

}

if (tempRlt[i] == 'b')

{

tempRlt[i - 1] = who[i - 1, flag];

}

}

result[k] = new String(tempRlt);

}

}

static void Main(string[] args)

{

const int N = 6;

int[] a = new int[N] { 2, 5, 7, 10, 5, 2 };

int[] b = new int[N] { 3, 8, 4, 11, 3, 4 };

int[] least = new int[N];

string[] result = new string[N];

DlrwZydd(a, b, N, least, result);

Console.WriteLine();

for (int i = 0; i < N; i++)

{

Console.WriteLine(" 按要求完成前{0}项任务的机器顺序为：" + result[i] + " 时间为：{1}" ,i+1,least[i]);

}

}

}

}