AI题库 · GESP-Python七级题库
题目分享 #16923
在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背包问题中,每个物品只能选择一次,并且子问题之间是独立的,无法重用计算结果。
AI题库 · 编程考级与信奥赛真题库
查看答案 →
复制链接后可在微信、QQ、小红书等平台粘贴分享;答案与解析在题目页。