K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
已知0-1背包问题中共有n个物品,背包最大承重为W,每个物品仅能被选取一次。下列关于该问题的动态规划求解说法正确的是?
二维动态规划数组dp[i][j]的含义是前j个物品放入承重为i的背包中的最大总价值,初始化时dp[0][] = 0且dp[][0] = 0
状态转移方程为当当前背包容量j >= 第i个物品重量时,dp[i][j] = max(dp[i-1][j], dp[i][j - weights[i]] + values[i])
使用一维空间优化后的dp数组求解0-1背包时,需要倒序遍历背包容量j,以确保每个物品仅被放入一次背包中
0-1背包问题的动态规划解法空间复杂度固定为O(nW),无法进行空间优化