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

批发站为取得最大总利润,应分配(__)。
本题考察的是资源分配的动态规划建模与求解。
设给甲、乙、丙、丁分别分配的箱数为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。
