K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
经典0-1背包问题要求每个物品仅可选择放入或不放入背包,现有关于其动态规划解法的四种描述,其中正确的是:
标准二维动态规划数组dp[i][j]表示前i个物品放入容量为j的背包所能获得的最大价值,初始化时dp[0][j](所有容量)和dp[i][0](所有物品数)均为0
状态转移方程为dp[i][j] = max(dp[i-1][j], dp[i][j - w[i]] + v[i]),该方程可直接用于0-1背包问题求解
将二维dp数组优化为一维空间时,遍历背包容量需要从前往后枚举,才能保证每个物品仅被放入一次
若物品重量数组为[1,2,3]、价值数组为[6,10,12],背包容量为5,则该问题的最大背包价值为24