在 背包问题中,给定一组物品,每个物品有一个重量和价值,背包的容量有限。假设背包的最大容量为 ,物品的数量为 ,其中第 个物品的重量为 ,价值为 。以下关于 背包问题的描述,正确的是()。
- A. 在解决 背包问题时,使⽤贪⼼算法可以保证找到最优解,因为物品只能放⼊⼀次。
- B. 背包是 问题(多项式时间可解问题),它可以在 的时间复杂度内解决。
- C. 背包问题中,动态规划解法的空间复杂度为 ,但可以通过滚动数组技巧将空间复杂度优化到 。
- D. 背包问题中,每个物品只能选择一次,并且子问题之间是独立的,无法重用计算结果。