某公司拟将5百万元资金投放下属A、B、C三个子公司(以百万元的倍数分配投资),各子公司获得部分投资后的收益如下表所示(以百万元为单位)。该公司投资的总收益至多为(__)百万元。

资源分配型动态规划(多项目投资类)是解决离散整数单位有限资源在多个对象间最优分配、以最大化总收益的核心方法,它将复杂的多对象分配问题拆解为逐次加入单个对象的分阶段子问题来递推求解。这类方法通常定义状态为仅考虑前i个对象、分配k单位资源时的最大收益,初始化规则为0个对象时无论分配多少资源收益均为0;状态转移时,通过枚举给当前对象分配的资源量,取前i-1个对象使用剩余资源的最大收益与当前对象对应资源量收益之和的最大值,来得到当前阶段的最优收益。该方法不仅适用于多子公司投资分配场景,还可推广到多生产任务原料分配、多门店铺货资金分配等各类离散资源最优分配问题,通过分阶段的局部最优选择累积得到全局最优解,尤其适配资源以整数倍数分配的离散场景。
本题考察的是资源分配型动态规划(多项目投资DP)。
设第i个子公司为A、B、C(i=1,2,3),总投资额为K=5(单位:百万元,整数)。
定义状态f(i,k)为“只考虑前i个子公司、总投资为k时的最大收益”,则状态转移为:f(i,k)=max_{0≤x≤k}[ f(i−1,k−x)+g_i(x) ],其中g_i(x)为给第i个子公司投入x时的收益。
初始化:f(0,k)=0。
按照A→B→C逐层计算:
A的收益(亦即f(1,k)):
k=0..5:0,1.2,1.8,2.5,3.0,3.5
将B并入,计算f(2,k):
k=0:0
k=1:max{1.2+0, 0+0.8}=1.2
k=2:max{1.8+0, 1.2+0.8, 0+1.5}=2.0
k=3:max{2.5+0, 1.8+0.8, 1.2+1.5, 0+3.0}=3.0
k=4:max{3.0+0, 2.5+0.8, 1.8+1.5, 1.2+3.0, 0+4.0}=4.2
k=5:max{3.5+0, 3.0+0.8, 2.5+1.5, 1.8+3.0, 1.2+4.0, 0+4.5}=5.2
再将C并入,计算f(3,k):
k=0:0
k=1:max{1.2+0, 0+1.0}=1.2
k=2:max{2.0+0, 1.2+1.0, 0+1.2}=2.2
k=3:max{3.0+0, 2.0+1.0, 1.2+1.2, 0+3.5}=3.5
k=4:max{4.2+0, 3.0+1.0, 2.0+1.2, 1.2+3.5, 0+4.2}=4.7
k=5:max{5.2+0, 4.2+1.0, 3.0+1.2, 2.0+3.5, 1.2+4.2, 0+4.8}=5.5
因此最大收益为5.5百万元。由k=5的最优取自f(2,2)+C投3可回溯出最优分配:A投1、B投1、C投3。
选择选项 D。
