单选题
适中
#19759
在0/1背包问题中,给定一组物品,每个物品有一个重量和价值,背包的容量有限。假设背包的最大容量为W,物品的数量为n ,其中第 个物品的重量为W[i],价值为 V…
在0/1背包问题中,给定一组物品,每个物品有一个重量和价值,背包的容量有限。假设背包的最大容量为W,物品的数量为n ,其中第 个物品的重量为W[i],价值为 V[i]。以下关于0/1背包问题的描述,正确的是( )。
答案与解析
正确答案:C
解析
0/1背包问题要求在容量限制下选择物品使总价值最大,每个物品至多选一次。该问题具有最优子结构和重叠子问题特性,适合用动态规划求解。状态定义为前i个物品在容量j下的最大价值,状态转移基于是否选取第i个物品。时间复杂度由状态数和转移代价决定,通常为O(nW)。空间上可利用二维数组存储中间结果,也可通过滚动数组压缩至一维,减少空间使用。贪心策略无法保证全局最优,因局部最优选择不必然导向整体最优。子问题虽独立定义,但计算过程中存在共享子结构,结果可被多次引用。