第28454题 单选题
下列关于0-1背包问题的动态规划实现描述中,正确的是?

已知0-1背包问题中共有n个物品,背包最大承重为W,每个物品仅能被选取一次。下列关于该问题的动态规划求解说法正确的是?

A

二维动态规划数组dp[i][j]的含义是前j个物品放入承重为i的背包中的最大总价值,初始化时dp[0][] = 0且dp[][0] = 0

B

状态转移方程为当当前背包容量j >= 第i个物品重量时,dp[i][j] = max(dp[i-1][j], dp[i][j - weights[i]] + values[i])

C

使用一维空间优化后的dp数组求解0-1背包时,需要倒序遍历背包容量j,以确保每个物品仅被放入一次背包中

D

0-1背包问题的动态规划解法空间复杂度固定为O(nW),无法进行空间优化

程序运行统计
暂无判题统计
提交0次 正确率0.00%
答案解析