第1页 / 共6页
第2页 / 共6页
第3页 / 共6页
第4页 / 共6页
第5页 / 共6页
第6页 / 共6页
动态规划求解资源分配问题.docx
一．实验目的
二、内容：
三、实验要求
四、实验步骤、结果与分析
五、实验心得
深 圳 大 学 实 验 报 告
课程名称：
算法设计与分析
实验名称：
动态规划
学院： 计算机与软件学院 专业： 计算机科学与技术
报告人：
学号：
班级：
同组人：
无
指导教师：
实验时间：
2017/11/10——2017/11/23
实验报告提交时间：
2017/11/23
教务处制
一．实验目的
（1）掌握动态规划算法设计思想。
（2）掌握资源分配问题的动态规划解法。
二、内容：
1、某厂根据计划安排，拟将 n 台相同的设备分配给 m 个车间，各车间获得这种设备后，可
以为国家提供盈利 Ci j(i 台设备提供给 j 号车间将得到的利润，1≤i≤n，1≤j≤m) 。问如何分配，
才使国家得到最大的盈利？
2、设计动态规划算法求解资源分配问题，写出求得最优值的递推公式。
3、对小规模问题利用蛮力法验证动态规划方法求解的正确性（即最优分配方案、最优分配
方案的值）。
4、测试不同问题规模（按级数增长）的运行时间。
5、能够实现的问题规模越大，成绩越高。
三、实验要求
1. 在blackboard提交电子版实验报告。
2. 源代码作为实验报告附件上传。
3. 在实验完成之后，将进行一次PPT介绍。
4. 实验成绩的给分标准是实验报告50%，PPT汇报50%。
四、实验步骤、结果与分析
1．蛮力法。
1.1 蛮力法思路。
将 n 台相同的设备分配给 m 个车间，假设不考虑设备不足的情况下，每间车间可以分配 0
到 n 台设备，共有（n+1）^m 种排列组合（即得到（n+1）叉树），最后排除设备分配总数
量>n 的分配方案，再从剩余的分配方案中筛选出能获得最大利润的分配方案，此时的分配
方案就是最优的。
force()：分配数据存储空间和数据初始化。
1.2.编写测试代码。
蛮力法代码编写主要分为两个函数模块：
1.
c[][]用于保存利润二维表，c[i][j]表示将 i 台设备分配给第 j 号车间时获得的利润；
x[]用于保存分配方式所获得利润，x[j]表示第 j 号车间获得利润；
num[]用于保存分配方式所分配的车间数，num[j]表示第 j 号车间所分配的设备数；
mx[]用于保存最大分配方式时的利润排列，mx[j]表示在最优资源分配时第 j 号车间所获得利
润；
pp[]用于保存最大分配方式时的设备排列，pp[j]表示在最优资源分配时第 j 号车间所分配的
设备数。
然后通过调用 place 模块，从第一间车间开始分配。
最后输出结果。
2. place()：递归求解，构造（n+1）叉树。（代码中用 cl 代替 j）
在这里递归停止条件为：当 m 间车间都分配完后就停止递归（车间号 j>m），然后计算该种
分配方式所获取的利润和需要的设备数，筛选出资源最优的分配方案和最大获利。
若当前车间号为 j（j<=m），则给该车间循环分配 0 到 n 台设备，保存该车间分配设备数和
获得利润，然后继续分配下一号车间。
1.2 实验结果截图。
当将 4 台设备分配给 3 个车间时：
1.3 性能分析。
由算法分析可知有 n 台设备、m 间车间时共有（n+1）^m 种排列组合，所以蛮力法的时间
复杂度为
O(n^m)
1.4 结论
n:m=3:1:
N
M
3
1
0
6
2
0
9
3
1
12
4
16
15
5
52
时间(ms)
3297
从表格中可以看到，用蛮力法解决资源分配问题只适用于解决很小规模的问题。
225699
2623
18
6
21
7
8
8
9
9
78377
2.动态规划算法。
2.1 动态规划算法思路。
动态规划需要达到两个条件：1.最优解结构；2.子问题叠加。因为每个子问题都是最优的，
所以可以将 m 个车间问题划分为前 m-1 个车间和第 m 个车间问题，每次分配第 m 个车间的
时候都是建立在前 m-1 的最优策略上，再进行最优分配。这样在迭代过程中就能保证每一
次都是最优的，从而最后达到整体最优。
进行最优分配时必须得到前 m-1 个车间的最优分配方案和最大利润，再与第 m 个车间进行
最优分配。所以在这里我需要建立三张表：c[][]、v[][]、p[][]，c[i][j]：第 j 号车间分配 i 台
设备可以获得的利润；v[i][j]：用 i 台设备分配给前 j 个车间的最大利润；p[i][j]：获得最优
解时第 j 号车间使用的设备数为 i-p[i][j]
假设求 v[i][j]（i 台设备分给 j 个车间），需要让 k 从 0 到 i，找出前 j-1 个车间分配设备数 k
时获得利润 v[k][j-1]与第 j 号车间分配设备数为 i-k 时获得利润 c[i-k][j]的和最大，所以最优
解结构为：
v[i][j] = max{v[k][j - 1] + c[i - k][j]} (1<=i<=n,1<=j<=m,0<=k<=i)
这时，j 号车间分配的设备数为 i-k
算法优化方案：
优化时间：在这里我们需要求得的最大利润为 v[n][m]，所以当求到最后一个车间时我们不
用求前 m 号车间分配 1…n-1 台设备时所获得的最大利润 v[1…n-1][m]
优化空间：
通过分析最优解结构公式可知，求前 j 号车间分配 i 台设备所获得的最大利润 v[i][j]只与前
一列求得的最大利润有关，与在 j-1 之前的最大利润无关，所以我们可以将二维数组 v[][]改
为一维数组 v[]，只存放前一列的数据。又因为求 v[i][j]是要与 v[0…i][j-1]比较，所以我们需
要从后往前覆盖（让 i 从 n 到 1），避免更新最大利润时造成数据丢失。
2.2. 编写测试代码。
1. 初始化三张表 c、v、p；
2. 三重 for 循环迭代求解问题。第一重对 1……m 间车间分别求解子问题，第二重对 n……
1 台设备分别求解最优子问题，第三重对 i 台设备循环求解出前 j-1 台设备与第 j 台设备
的最优分配方案。
实际代码（已优化）为：
for (j = 1; j < m + 1; j++)
for (i = n; i >= 1; i--){
if (j == m&&i < n)
break;
else{
int max = 0;
for (k = i; k >= 0; k--)
if (max < v[k] + c[i - k][j])
{
max = v[k] + c[i - k][j];
v[i] = max;
p[i][j] = k;
}
}
}
3. 输出结果。
2.2 实验结果截图。
2.3 性能分析。
时间复杂度为
通过分析三重循环我们可以这样计算时间复杂度：
(m-1)*[(n+1)+n+(n-1)+…+3+2]+(n+1)=(m-1)*(1/2*n^2+3/2*n)+(n+1)
即 O(m*n^2)
空间复杂度为 O(n*m)
2.4 结论
n:m=3:1:
N
M
3
1
0
9
3
0
15
5
16
21
7
20
时间(ms)
从表格中可知，用动态规划法解决资源分配问题对于一万规模以下的问题效率很高，但一旦
到了十万规模以上程序就不能实现了。
30
10
24
300
100
147
3000
1000
4064
1000
10000
33763
五、实验心得
通过本次实验，我掌握了动态规划算法设计思想，并掌握了资源分配问题的动态规划解
法和蛮力解法。
指导教师批阅意见：
成绩评定：
备注：
指导教师签字：
年
月
日
注：1、报告内的项目或内容设置，可根据实际情况加以调整和补充。
2、教师批改学生实验报告时间应在学生提交实验报告时间后 10 日内。
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
