查看更多
当前 - 选择题 - 动态规划
困难
单选题
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百万元。

联系我们
隐私协议
用户协议
微信公众号
知乎
小红书
浙ICP备2021029036号
@2022-2026
嘉兴市安芯网络科技有限公司 版权所有