K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
已知0-1背包问题中每个物品仅能被选取一次,以下关于其动态规划求解的描述正确的是:
使用二维动态规划数组dp[i][j]表示前i个物品放入容量为j的背包的最大价值,当j >= w[i]时,状态转移方程为dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])
dp[i][j]
i
j
j >= w[i]
dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])
使用滚动数组优化0-1背包的空间复杂度时,遍历背包容量的顺序可以从前往后进行
0-1背包问题允许每个物品被多次放入背包中
二维dp数组的初始化应全部赋值为1,代表初始时背包的最大价值为1