分别用贪心算法、动态规划法、回溯法设计0-1背包问题。要求:说明所使用的算法策略;写出算法实现的主要步骤;分析算法的时间。
正确答案:(1)贪心算法O(nlog(n))
首先计算每种物品单位重量的价值Vi/Wi,然后,依贪心选择策略,将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后,背包内的物品总重量未超过C,则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去,直到背包装满为止。
具体算法可描述如下:
(2)动态规划法O(nc)
M(i,j)是背包容量为j,可选择物品为i,i+1,…,n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质,可以建立计算m(i,j)的递归式如下。
(3)回溯法O(2n)
首先计算每种物品单位重量的价值Vi/Wi,然后,依贪心选择策略,将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后,背包内的物品总重量未超过C,则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去,直到背包装满为止。
具体算法可描述如下:
(2)动态规划法O(nc)
M(i,j)是背包容量为j,可选择物品为i,i+1,…,n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质,可以建立计算m(i,j)的递归式如下。
(3)回溯法O(2n)
答案解析:有
微信扫一扫手机做题