扫一扫二维码
进群一起备考
查看更多
当前 - 选择题 - 动态规划困难
单选题
2016年5月第37题
收藏
分享
#数学与经济管理
#动态规划
#凯恩建议了解即可
#教材之外（超纲）
用一辆载重量为10吨的卡车装运某仓库中的货物（不用考虑装车时货物的大小），这些货物单件的重量和运输利润如下表。适当选择装运一些货物各若干件，就能获得最大总利润（__）元。
问题（1）
正确答案D
凯恩解析
本题考察的是背包问题（无限件/完全背包）的优化计算。
设 f[t] 表示容量 t 吨的最大利润。初始化 f[0]=0；对每个物品（A…F），按容量从小到大更新 f（完全背包的标准顺序）：
f[t]=max(f[t], f[t−w_i]+v_i)。计算到 t=10，可得到
f[0..10]=0, 53, 106, 159, 216, 269, 322, 375, 432, 485, 538。
其中 f[10]=538，于 t=10 处的最优转移来自 f[6]+D 或 f[8]+A+A，均对应2D+2A。