算法设计与分析 课件 10.4-综合应用-资源分配问题

信息工程大学算法设计与分析综合应用—资源分配问题国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版

有一笔资金共计m份，现给n个工程项目投资，给第i项工程投资资金j(份)所得的收益用p(i,j)(i,j为非负整数)表示。问应该如何分配资金，使得投资的收益最大。

比如m=4，n=3时，p(i,j)如下表所示，给工程1、2、3分别分配资金1、1、2时获得最大收益为43。投资金额01234工程1收益013151922工程2收益01213.514.516工程3收益014182124分配资金的方法很多，从中选择收益最大的。该问题是一个最优化问题，如果符合最优子结构性质，进一步判断是否可用动态规划和贪心法求解。该问题也是一个搜索问题，可以用回溯法、分支限界求解。结合实例分析：当m=4，n=3时，对应的最优解为（1，1，2），那么，(1,1)是2份资金给工程1、2投资对应的最佳分配方案。投资金额01234工程1收益013151922工程2收益01213.514.516工程3收益014182124单选题。在资源分配问题中，当m=4，n=3时，对应的最优解为（1，1，2），以下说法错误的是（）。A.(1,2)是3份资金给工程1和工程3投资对应的最佳分配方案。B.(1,2)是3份资金给工程2和工程3投资对应的最佳分配方案。C.(1,1)是3份资金给工程1和工程3投资对应的最佳分配方案。

j=0j=1j=2j=3j=4i=00/00/00/00/00/0i=10/013/115/219/322/4i=20/013/025/127/131/1i=30/014/127/139/143/2投资金额01234工程1利润013151922工程2利润01213.514.516工程3利润014182124f[i][j]/s[i][j]收益表：p[i][j]时间复杂度是O(m2n)方法二：贪心法

贪心选择策略：在每分配1份资金时优先选择收益增量最大的工程。投资金额增量1111工程1收益增量13243工程2收益增量121.511.5工程3收益增量14433投资金额01234工程1利润013151922工程2利润01213.514.516工程3利润014182124收益表：p[i][j]收益增量表投资金额增量1111工程1收益增量13243工程2收益增量121.511.5工程3收益增量14433收益增量表贪心法的求解过程时间复杂度是O(mn)收益14收益13收益12收益4方法三：回溯法

解向量为(x1,x2,…,xi,…,xn)，xi表示给工程i分配的资金数目，xi=0~m且xi为整数。资源分配问题的解空间树是一棵子集树。

约束函数为：已分配的资金总和小于总资金数，如果等于总资金数则说明找到了一个可行解。

在搜索过程中，不断更新当前最大收益，直至整棵树搜索完毕，即可得到最优解。最坏时间复杂度是O((m+1)n)方法四：分支限界法以当前已经得到的收益作为优先值，这个数值越大，搜索的优先级越高，可以采用优先队列式分支限界法实现。最坏时间复杂度是O((m+1)n)算法分析问题的出发点最坏时间复杂度动态规划问题具有最优子结构性质