K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
已知背包最大承重为4,现有3个物品:物品1(重量2,价值3)、物品2(重量3,价值4)、物品3(重量1,价值2),以下关于该场景下0-1背包的动态规划实现描述正确的是:
使用一维滚动数组优化0-1背包时,需要正序遍历背包容量从1到4,以最大化利用空间
二维动态规划数组的初始化应设置dp[0][j] = 0(所有j≥0)和dp[i][0] = 0(所有i≥0),即没有物品或背包承重为0时最大价值为0
当当前物品重量大于背包容量j时,dp[i][j] = dp[i][j-1]
标准递推式为dp[i][j] = max(dp[i-1][j], dp[i][j - weight[i]] + value[i])