GESP 1-4级 -- GESP 5-8级 -- CSP-J/S --

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

单选题困难

知识点

动态规划 0/1背包状态转移

题目描述

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

选项（单选）

A

在解决0/1背包问题时，使用贪⼼算法可以保证找到最优解，因为物品只能放⼊一次。

B

0/1背包是P问题（多项式时间可解问题），它可以在O(nW)的时间复杂度内解决。

C

0/1背包问题中，动态规划解法的空间复杂度为O(nW) ，但可以通过滚动数组技巧将空间复杂度优化到O(W) 。

D

0/1背包问题中，每个物品只能选择一次，并且⼦问题之间是独⽴的，无法重用计算结果。

上一题下一题