单选题 适中
#16923

在0/1背包问题中,给定一组物品,每个物品有一个重量和价值,背包的容量有限。假设背包的最大容量为 W,物品的数量为 n,其中第 i个物品的重量为 w[i],价值…

在0/1背包问题中,给定一组物品,每个物品有一个重量和价值,背包的容量有限。假设背包的最大容量为 W,物品的数量为 n,其中第 i个物品的重量为 w[i],价值为 v[i]。以下关于0/1背包问题的描述,正确的是( )。

未登录也能判分,登录后才会记录
答案与解析
正确答案:C
解析
分析0/1背包问题的求解机制。该问题涉及在容量限制下选择物品以最大化总价值,每个物品仅可选一次。动态规划通过构建状态表记录前i个物品在不同重量限制下的最优价值,状态转移基于是否放入第i个物品。状态表的行对应物品数量,列对应重量范围,时间复杂度由物品数和容量决定。空间优化可通过滚动数组实现,利用当前状态仅依赖前一状态的特性,压缩存储维度。贪心策略无法保证最优解,因局部最优选择不必然导向全局最优。子问题具有重叠性,计算结果可被多次引用。问题不属于P类,因其多项式时间算法依赖数值输入而非输入长度。