在0/1背包问题中,给定一组物品,每个物品有一个重量和价值,背包的容量有限。假设背包的最大容量为 WWW,物品的数量为 nnn,其中第 iii 个物品的重量为 w[i]w[i]w[i],价值为 v[i]v[i]v[i]。以下关于0/1背包问题的描述,正确的是( )。
在解决0/1背包问题时,使用贪心算法可以保证找到最优解,因为物品只能放入一次。
0/1背包是P问题(多项式时间可解问题),它可以在 O(nW)O(nW)O(nW) 的时间复杂度内解决。
0/1背包问题中,动态规划解法的空间复杂度为 O(nW)O(nW)O(nW),但可以通过滚动数组技巧将空间复杂度优化到 O(W)O(W)O(W)。
0/1背包问题中,每个物品只能选择一次,并且子问题之间是独立的,无法重用计算结果。