通过动态规划方法解决资源分配问题。

简介：
实验课程：算法分析与设计实验名称：运用动态规划法解决资源分配难题（验证性实验）实验目标：（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]，从而可以通过从结果倒推往回求的方式得到最终的分配方案。程序实现时采用顺推法,首先枚举车间的数量,然后枚举设备的数量,最后在状态转移时用到的设备数,可以使用简单的三重for循环语句来完成程序实现. 该算法的时间复杂度为O(n^2*m)，空间复杂度为O(n*m)。如果此题只需求最大获利而不必求具体的方案,则状态量可以减少一维,从而优化空间复杂度为O(n)。