赞题库-背景图
单项选择题

考虑一个背包问题,共有n=5个物品,背包容量为W=10,物品的重量和价值分别为:w={2,2,6,5,4},v={6,3,5,4,6},求背包问题的最大装包价值。若此为0-1背包问题,分析该问题具有最优子结构,定义递归式为

其中c(i,j)表示i个物品、容量为j的0-1背包问题的最大装包价值,最终要求解c(n,W)。

采用自底向上的动态规划方法求解,算法的时间复杂度为()。

A.Θ(nW)
B.Θ(nlgn)
C.Θ(n2
D.Θ(nlgnW)