用动态规划法与回溯法实现0-1背包问题论文
编辑：
2015-05-15
(4)根据计算最优值时到得的信息，构造最优解。
对于所给0-1背包问题的子问题：
，
的最优值为m(i，j)，即m(i，j)是背包容量为j，可悬着物品为i,i+1,….,n时0-1背包问题的最优值。由于0-1背包问题的最优子结构性质，可以建立计算m(i，j)的如下递归式：
(1.1)
(1.2)
从上面算法的执行过程中可以看出假设有Q(n)个子问题,每一个子问题最多需要m次决策,则计算的频率为nm,回溯的频率为n，那么整个过程的算法的时间复杂度为T(n)=nm+n，即为Q(nm)。
编辑老师为大家整理了用动态规划法与回溯法实现0-1背包问题，希望对大家有所帮助。
相关推荐：
标签：计算机教育论文
免责声明
威廉希尔app (51edu.com)在建设过程中引用了互联网上的一些信息资源并对有明确来源的信息注明了出处，版权归原作者及原网站所有，如果您对本站信息资源版权的归属问题存有异议，请您致信qinquan#51edu.com(将#换成@)，我们会立即做出答复并及时解决。如果您认为本站有侵犯您权益的行为，请通知我们，我们一定根据实际情况及时处理。