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

经典0-1背包问题要求每个物品仅可选择放入或不放入背包,现有关于其动态规划解法的四种描述,其中正确的是:

A

标准二维动态规划数组dp[i][j]表示前i个物品放入容量为j的背包所能获得的最大价值,初始化时dp[0][j](所有容量)和dp[i][0](所有物品数)均为0

B

状态转移方程为dp[i][j] = max(dp[i-1][j], dp[i][j - w[i]] + v[i]),该方程可直接用于0-1背包问题求解

C

将二维dp数组优化为一维空间时,遍历背包容量需要从前往后枚举,才能保证每个物品仅被放入一次

D

若物品重量数组为[1,2,3]、价值数组为[6,10,12],背包容量为5,则该问题的最大背包价值为24

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