logo资料库

用动态规划法求解资源分配问题.doc

发布时间：2022-06-13 发布人：admin 分类：说明书 资料大小：0.86M 资料格式：doc 举报 版权申诉
第1页 / 共11页
第2页 / 共11页
第3页 / 共11页
第4页 / 共11页
第5页 / 共11页
第6页 / 共11页
第7页 / 共11页
第8页 / 共11页
资料共11页，剩余部分请下载后查看
    华南师范大学本科生实验报告 姓名＿林少油 ＿ 学号 20102100076 院系＿计算机学院＿ 专业＿嵌入式 ＿ 年级 2010 级 班级＿3 班 小组实验任务分工＿ 独立完成 实验时间 2012 年＿5 月 12＿日 实验名称 动态规划的应用 指导老师及职称 陈卫东 副教授 华南师范大学教务处编印
    实验课程：算法分析与设计 实验名称：用动态规划法求解资源分配问题 （验证型实验） 实验目标： （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) 。问如 何分配，才使国家得到最大的盈利？ 算法基本思想： 本问题是一简单资源分配问题，由于具有明显的最优子结构，故可以使用动态规划求解， 用 状 态 量 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 using namespace std; #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<<"实例"<
    cout<= 1; --j) { cout<
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料