在解决0/1背包问题时,使用贪心算法可以保证找到最优解,因为物品只能放入一次。
0/1背包是P问题(多项式时间可解问题),它可以在 O(nW) 的时间复杂度内解决。
0/1背包问题中,动态规划解法的空间复杂度为 O(nW),但可以通过滚动数组技巧将空间复杂度优化到 O(W)。
0/1背包问题中,每个物品只能选择一次,并且子问题之间是独立的,无法重用计算结果。