查看更多
当前 - 选择题 - 动态规划
困难
单选题
2014年5月第42题
#数学与经济管理
#动态规划
#凯恩建议了解即可
#教材之外(超纲)

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

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

问题(1)
正确答案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
嘉兴市安芯网络科技有限公司 版权所有