博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
2017.10.2 计算机算法分析----0-1背包问题
阅读量:5328 次
发布时间:2019-06-14

本文共 535 字,大约阅读时间需要 1 分钟。

回溯算法的要点:

1,针对所给问题,定义问题的解空间。

2,确定容易搜索的解空间的组织结构。

3,通过剪枝优化搜索过程。

下面通过求解0/1背包问题来分析使用回溯算法的过程:

1,根据问题的描述,设所有的物件数是N,对应的重量和价值分别为w[0~N-1]和v[0~N-1],于是这个问题就转化成在这N件物件中选择一个子集,使其总价值最大,并且满足总重量不超过包的容量cw。因此此问题的解空间是2^n。

2,对于从n个元素的集合S中求满足某种性质的子集时,相应的子空间成为子集树,这类子集树通常是满完全二叉树,通过遍历这棵树的每个叶子节点来达到遍历整个解空间的目的,相应的时间复杂度为O(2^n)。

3,对于背包问题的剪枝函数,可以从以下两方面考虑:

(1)根据题目要求,选择物件的总重量不能超过包的容积,这可以作为一个剪枝条件。用Constraint(t)函数表示在遍历子集树第t层某个节点时,此约束函数是否满足,如不满足,则剪去相应的子树。

(2)第二种剪枝函数称为边界函数Bound(t),当它返回true时,表示当前遍历节点未取得最优值,需要进一步搜索子树。

转载于:https://www.cnblogs.com/qichunlin/p/7622912.html

你可能感兴趣的文章
时间管理(二):时间管理的六项基本原则
查看>>
iOS8 自定义navigationbar 以及 UIBarButtonItem 边距问题
查看>>
iOS多线程编程--NSOperation(转)
查看>>
高可用Redis(四):列表,集合与有序集合
查看>>
进程线程之pid,tid
查看>>
立即执行函数
查看>>
rsync使用详解
查看>>
SVN常用命令
查看>>
bzoj3223Tyvj 1729 文艺平衡树 splay
查看>>
七夕心形demo
查看>>
Python垃圾回收机制:gc模块
查看>>
使用ifconfig命令来看网卡的IP,但是,输入命令之后,eht0里面只有 inet6 addr 而没有 inet addr...
查看>>
VsCode云端版本
查看>>
MyBatis学习--查询缓存
查看>>
Java实现快速排序
查看>>
python学习笔记--python数据类型
查看>>
Java学习总结
查看>>
一些忘记了的....
查看>>
Codeforces 448E Divisors
查看>>
linux高级技巧:rsync同步(二)
查看>>