动态规划求解资源分配实验报告.doc

- -

动态规划求解资源分配

实验目标：

（）掌握用动态规划方法求解实际问题的基本思路。

（）进一步理解动态规划方法的实质，巩固设计动态规划算法的基本步骤。

实验任务：

（）设计动态规划算法求解资源分配问题，给出算法的非形式描述。

（） 在  环境下用 C语言实现该算法。计算  个实例，每个实例中 n，

；等编程语言。

实验主要步骤：

 认真阅读实验目的与实验任务，明确本次实验的内容；

 分析实验中要求求解的问题，根据动态规划的思想，得出优化方程；

 从问题出发，设计出相应的动态规划算法，并根据设计编写程序实现算法；

 设计实验数据并运行程序、记录运行的结果；

 分析算法的时间和空间复杂度，并由此解释释相应的实验结果；

问题描述：资源分配问题

某厂根据计划安排，拟将 n 台相同的设备分配给 m 个车间，各车间获得这种设备后，

可以为国家提供盈利 C

i 台设备提供给 j 号车间将得到的利润，in，jm。问如

用的设备数为 #&，于是从结果倒推往回求即可得到分配方案。程序实现时使用顺推 ，

先枚举车间数，再枚举设备数，再枚举状态转移时用到的设备数，简单  重 ' 循环语句

- 考试资料