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

用一辆载重量为10吨的卡车装运某仓库中的货物(不用考虑装车时货物的大小),这些货物单件的重量和运输利润如下表。适当选择装运一些货物各若干件,就能获得最大总利润(__)元。

问题(1)
浓缩知识点

完全背包问题是动态规划经典题型,核心特征是每种物品可重复选取,目标是在给定容量限制下,选取物品组合以获取最大价值或利润。这类问题通常用动态规划解法,定义状态f[t]为容量为t时能获得的最大价值,初始化f[0]=0,即容量为0时价值为0。求解时按物品顺序遍历,对每个物品,从容量小到大地更新状态数组,以此实现同一物品的重复选取计算,状态转移核心是对每个容量t,比较不选当前物品的价值f[t]与选取至少一件当前物品的价值f[t-物品重量]+物品价值,取较大值更新f[t]。它和0-1背包的关键区别在于容量遍历顺序,0-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

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