K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
现有一个0-1背包问题,背包最大承重为5,共有3个可选物品:物品1(重量2,价值3)、物品2(重量3,价值4)、物品3(重量1,价值2)。以下关于该问题动态规划实现的选项中,正确的是:
二维DP数组dp[i][j]表示前i个物品放入容量为j的背包的最大价值,初始化dp[0][j]=0(所有j≥0)、dp[i][0]=0(所有i≥0);递推规则为:当当前物品重量>j时,dp[i][j] = dp[i-1][j];否则dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i-1]] + value[i-1])
使用滚动数组优化空间时,需要从小到大遍历背包容量,这样可以避免重复计算前i个物品的状态
若使用二维DP数组,处理完第1个物品后,当背包容量为2时,dp[1][2]的结果为2
该0-1背包问题的最终最大价值为6