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

动态规划求解资源分配动态规划求解资源分配 实验目标 实验目标 1 掌握用动态规划方法求解实际问题的基本思路 2 进一步理解动态规划方法的实质 巩固设计动态规划算法的基本步骤 实验任务 实验任务 1 设计动态规划算法求解资源分配问题 给出算法的非形式描述 2 在 Windows 环境下用 C 语言实现该算法 计算 10 个实例 每个实例中 n 30 m 10 Ci j为随机产生于范围 0 103 内的整数 记录各实例的数据及执行结果 即最 优分配方案 最优分配方案的值 运行时间 3 从理论上分析算法的时间和空间复杂度 并由此解释相应的实验结果 实验设备及环境实验设备及环境 PC C C 等编程语言 实验主要步骤 实验主要步骤 1 认真阅读实验目的与实验任务 明确本次实验的内容 2 分析实验中要求求解的问题 根据动态规划的思想 得出优化方程 3 从问题出发 设计出相应的动态规划算法 并根据设计编写程序实现算法 4 设计实验数据并运行程序 记录运行的结果 5 分析算法的时间和空间复杂度 并由此解释释相应的实验结果 问题描述 资源分配问题问题描述 资源分配问题 某厂根据计划安排 拟将 n 台相同的设备分配给 m 个车间 各车间获得这种设备后 可以为国家提供盈利 Ci j i 台设备提供给 j 号车间将得到的利润 1 i n 1 j m 问如何 分配 才使国家得到最大的盈利 1 问题分析 本问题是一简单资源分配问题 由于具有明显的最优子结构 故可以使用动态规划求 解 用状态量 f i j 表示用 i 台设备分配给前 j 个车间的最大获利 那么显然有 f i j max f k j 1 c i k j 0 k i 再用 p i j 表示获得最优解时第 j 号车间使用的设备 数为 i p i j 于是从结果倒推往回求即可得到分配方案 程序实现时使用顺推 先枚举车 间数 再枚举设备数 再枚举状态转移时用到的设备数 简单 3 重 for 循环语句即可完成 时间复杂度为 O n 2 m 空间复杂度为 O n m 倘若此题只需求最大获利而不必求方案 则状态量可以减少一维 空间复杂度优化为 O n 程序代码 程序代码 include include include include include define N 31 define M 11 int c N M f N M p N M int main int i j n m k srand time NULL n 30 m 10 for int cas 1 cas 5 cas cout 第 cas 个实例 endl memset c 0 sizeof c for i 1 i n i for j 1 j m j c i j rand 1000 cout 利润表 endl cout for j 1 j m j cout setw 4 j cout endl for i 1 i n i cout setw 4 i for j 1 j m j cout setw 4 c i j cout endl memset f 0 sizeof f memset p 1 sizeof p for j 1 j m j for i 1 i n i for k 0 k i k if f i j f k j 1 c i k j f i j f k j 1 c i k j p i j k cout 最大获利 f n m endl cout 资源分配匹配方案 1 j cout 第 j 号车间使用 k p k j 台设备 endl k p k j cout endl return 0 实验小结 实验小结 本次是