查看更多
当前 - 选择题 - 动态规划
困难
单选题
2014年5月第42题
#了解即可
#超纲

某批发站准备向甲、乙、丙、丁四家小商店供应5箱商品。批发站能取得的利润(单位:百元)与分配的箱数有关(见下表)。

批发站为取得最大总利润,应分配(__)。

问题(1)
浓缩知识点

资源分配类动态规划是解决有限资源分配给多个目标、追求最优收益(或最小成本)的经典方法,可应用于物资调配、生产任务分配、资金分配等场景。这类问题的核心是将复杂的全局分配问题拆解为逐步叠加分配对象的子问题,具体要点包括:首先定义状态,一般设dp[i][j]表示将j单位资源分配给前i个对象的最优收益;其次确定转移逻辑,dp[i][j]的最优值由所有可能的分配情况中选取,即给第i个对象分配k单位资源时,前i-1个对象分配j-k单位的最优收益加上第i个对象分k单位的收益,取其中的最值;初始状态设为dp[0][j]=0,代表0个对象分配任何资源的收益为0。计算时按分配对象的顺序逐层推导状态值,从只考虑第一个对象的情况开始,逐步叠加后续对象,最终得到所有资源分配给全部对象的全局最优值。若需确定具体分配方案,可通过回溯法从最终状态倒推,依次确定每个对象的最优分配量。此外,需提前整理好每个对象分配不同单位资源的累计收益表(包含分配0单位的收益0),这是整个计算的基础数据支撑。

正确答案
C

本题考察的是资源分配的动态规划建模与求解
设给甲、乙、丙、丁分别分配的箱数为x₁,x₂,x₃,x₄,且x₁+x₂+x₃+x₄=5,xᵢ≥0。各店“给k箱”的累计利润为:甲[0,4,6,7,7,7],乙[0,2,4,6,8,9],丙[0,3,6,7,8,8],丁[0,4,5,6,6,6](k=0…5,k=0时利润为0)。
定义状态dp[i][j] 为“把前i家商店分配j箱所能取得的最大利润”。转移方程为
dp[i][j] = max₀≤k≤j { dp[i−1][j−k] + profitᵢ[k] }。
初值:dp[0][j]=0。

按商店顺序(甲→乙→丙→丁)逐层计算。
加入甲后得到 dp[1][0..5] = [0,4,6,7,7,7]。

在此基础上加入乙,逐j枚举k,有 dp[2][0..5] = [0,4,6,8,10,12]。

再加入丙,计算得 dp[3][0..5] = [0,4,7,10,12,14]。
最后加入丁,计算得 dp[4][0..5] = [0,4,8,11,14,16]。因此最大总利润为16(百元)。

由最后一步回溯构造最优分配:dp[4][5]=16 由分给丁1箱得到(dp[3][4]=12 + 丁分1箱得4);
而 dp[3][4]=12 由分给丙2箱得到(dp[2][2]=6 + 丙分2箱得6);
再由 dp[2][2]=6 可取两种等价选择:要么甲2箱、乙0箱(6+0),要么甲1箱、乙1箱(4+2)。
于是存在两种最优方案:
甲2、乙0、丙2、丁1;或 甲1、乙1、丙2、丁1。两者总利润均为16(百元)。
选择选项 C。

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