【单选题】考虑一个背包问题,共有n=5个物品,背包容量为W=10,物品的重量和价值分别为:w={2,2,6,5,4},v={6,3,5,4,6},求背包问题的最大装包价值。若此为0-1背包问题,分析该问题具有最优子结构,定义递归式为 其中c(i,j)表示i个物品、容量为j的0-1背包问题的最大装包价值,最终要求解c(n,W)。 采用自底向上的动态规划方法求解,得到最大装包价值为(62),算法的时间复杂度为(...
【简答题】考虑一个背包问题,共有 n=5 个物品,背包容量为 W= 10 ,物品的重量和价值分别为: w={2 , 2 , 6 , 5 , 4} , v={6, 3 , 5 , 4 , 6} ,求背包问题的最大装包价值。若此为 0-1 背包问题,分析该问题具有最优子结构,定义递归式为 其中 c ( i , j )表示 i 个物品、容量为 j 的 0-1 背包问题的最大装包价值,最终要求解 c ( n,W )...