题目内容
（请给出正确答案）
提问人：网友黄平
发布时间：2022-01-07
[单选题]
有载重量为 M 的背包,n 种物品的重量及价值分别
有载重量为 M 的背包,n 种物品的重量及价值分别
。如果每个物品只有一件,求一种最优装法,使得装入背包的物体价值最大。考虑回溯算法。先对物品按照
从大到小进行排序,并用序列＜ 重量,价值 ＞来表示排好序以后的物品序列。对如下给定实例:
排序后的结果是:
用
=1或 0来分别表示取用或者不用物品 i。那么在搜索树的节点
处的代价函数为:
A.
B.
C.
D.
参考答案
简答题官方参考答案
（由简答题聘请的专业题库老师提供的解答）
查看官方参考答案
网友提供的答案
共位网友提供了参考答案，
查看全部
- · 有5位网友选择 C，占比55.56%
- · 有2位网友选择 B，占比22.22%
- · 有1位网友选择 A，占比11.11%
- · 有1位网友选择 D，占比11.11%
，体积是
，价值为
，每种物品只有1个。背包的重量限制为W，容积限制为V。问如何选择装入背包的物品，使得背包物品的总价值最大？ 设
表示使用前i种物品、背包重量限制为j、容积为k时的最大价值，其中
那么递推方程是：
，体积是
，价值为
，每种物品只有1个。背包的重量限制为W，容积限制为V。问如何选择装入背包的物品，使得背包物品的总价值最大？ 设
表示使用前i种物品、背包重量限制为j、容积为k时的最大价值，其中
那么递推方程是：
，体积是
，价值为
，每种物品只有1个。背包的重量限制为W，容积限制为V。 设
表示使用前i种物品、背包重量限制为j、容积为k时的最大价值，其中
那么递推方程是：
考虑上述的二维0-1背包问题，动态规划算法的时间复杂度是：
,
使得
,而且
达到最大.因此,0-1背包问题是一个特殊的整数规划问题.
,要求n元0-1向量
,
使得
而且
达到最大.
