扫一扫二维码
进群一起备考
查看更多
当前 - 选择题 - 动态规划困难
单选题
2016年11月第46题
收藏
分享
#数学与经济管理
#动态规划
#凯恩建议了解即可
#教材之外(超纲)
某公司有4百万元资金用于甲、乙、丙三厂追加投资。各厂获得不同投资款后的效益见下表。适当分配投资(以百万元为单位)可以获得的最大的总效益为(__)百万元。

问题(1)
正确答案C
凯恩解析
本题考察的是资源分配类动态规划(投资组合优化) 的建模与求解。
设dp[i][j]表示把总资金j(0≤j≤4)分配给前i个工厂(按顺序为甲、乙、丙中的第i个)的最大效益。根据题表可得甲、乙、丙在0~4百万元投资下的效益函数值,状态转移为:dp[i][j] = max₀≤k≤j{ dp[i−1][j−k] + value_i(k) }。
解题思路:先用甲厂初始化,再依次并入乙、丙两厂。由题表可读出甲在0~4时效益分别为3.8、4.1、4.8、6.0、6.6;乙在0~4时分别为4.0、4.2、5.0、…(据表取值);丙在0~4时分别为4.8、6.4、6.8、7.8、7.8。
甲厂初始化得到dp[1][j](即仅投甲):dp[1][0]=3.8,dp[1][1]=4.1,dp[1][2]=4.8,dp[1][3]=6.0,dp[1][4]=6.6。
将乙厂并入,按转移式逐j枚举k求最大值,可得dp[2][3]=10.0(对应将3百万元全部给甲、乙为0);dp[2][4]=11.4(最佳拆分见表计算)。
再将丙厂并入,计算dp[3][4]:当给丙0~4百万元时得到的候选值分别为16.2、16.4、15.8、15.9、15.6,最大为16.4,对应分配方案为甲3、乙0、丙1(效益6.0+4.0+6.4=16.4)。
因此,最大总效益为16.4百万元。
