下列关于01背包问题的动态规划空间优化实现，说法正确的是？

tm965889 单选题共个子题

已知常规二维动态规划求解01背包的核心代码如下：

int dp[1005][1005] = {0};
for(int i = 1; i <= n; i++){
    for(int j = 0; j <= V; j++){
        if(j < w[i]) dp[i][j] = dp[i-1][j];
        else dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]);
    }
}

其中w为物品重量数组，v为物品价值数组，V为背包总容量，n为物品总数。若将该二维DP数组优化为一维数组实现，以下优化后的代码正确的是：

使用一维数组dp[1005]，保留原循环顺序：i从1到n，j从0到V，代码为dp[j] = max(dp[j], dp[j - w[i]] + v[i])

使用一维数组dp[1005]，i从1到n，j从V到w[i]，代码为dp[j] = max(dp[j], dp[j - w[i]] + v[i])

使用一维数组dp[1005]，i从1到n，j从0到V，代码为dp[j] = max(dp[j], dp[j - w[i]] + v[i])

使用一维数组dp[1005]，调换循环顺序：j从0到V，i从1到n，代码为dp[j] = max(dp[j], dp[j - w[i]] + v[i])

正在加载题目数据…

第空

已答 /

子题

第空

提示

该题型需在试卷/作业中作答，单题练习暂不支持

答案解析

New