针对0-1背包问题的动态规划空间优化,下列说法正确的是?

rm061017 单选题 共 个子题

已知经典0-1背包问题的二维动态规划解法使用dp[i][j]表示前i件物品放入容量为j的背包可获得的最大价值,其空间复杂度为O(nm)(n为物品数量,m为背包总容量)。若将其空间优化至O(m),下列描述正确的是?

A

优化后遍历背包容量j时,从小到大遍历与从大到小遍历结果一致

B

优化后必须从大到小遍历背包容量j,才能保证同一物品不会被多次放入背包

C

该空间优化方法仅适用于0-1背包问题,无法推广到其他动态规划场景

D

优化后的一维dp数组无法再进行任何空间压缩

正在加载题目数据…
已答 /
子题
该题型需在试卷/作业中作答,单题练习暂不支持
答案解析
讨论
发布
登录后参与讨论 立即登录
发布讨论需先绑定并验证手机号 去绑定手机号
加载中…
我
我
回复 @
回复 @
发送
还没有人讨论,来发表第一条吧