没有合适的资源?快使用搜索试试~ 我知道了~
贪心算法 动态规划算法 回溯法 分支-限界法 带代码 贪心算法总是作出在当前看来是最好的选择,即贪心算法并不从整体最优解上加以考虑,它所作出的选择只是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,但对范围相当广的许多问题它能产生整体最优解。在一些情况下,即使贪心算法不能得到整体最优解,但其最终结果却是最优解的很好近似解。动态规划算法的基本思想是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法。它把已知问题分为很多子问题,按顺序求解子问题,在每一种情况下,列出各种情况的局部解,按条件从中选取那些最有可能产生最佳的结果舍弃其余。前一子问题为后面子问题提供信息,而减少计算量,最后一个子问题的解即为问题解。
资源推荐
资源详情
资源评论
- 1 -
-
《算法分析与设计》课程设计
学 院:
专 业: 计算机科学与技术
年 级: 级
姓 名:
设计题目: 0-1 背包问题的四种算法实现
指导教师: 职称:
成 绩:
2020 年 6 月 27 日
0-1 背包问题的四种算法实现
1. 需求分析
1.1 问题描述
学号:
- 2 -
1、0—1 背包问题:给定 n 种物品和一个背包,背包最大容量为 M,物品 i 的重量
是 w
i
,其价值是平 P
i
,问应当如何选择装入背包的物品,似的装入背包的物品的总
价值最大?
背包问题的数学描述如下:
2、要求找到一个 n 元向量(x1,x2…xn),在满足约束条件:
情况下,使得目标函数 ,其中,1 i n;M>0;wi>0;
pi>0。满足约束条件的任何向量都是一个可行解,而使得目标函数达到最大的那个
可行解则为最优解
[1]
。
给定 n 种物品和 1 个背包。物品 i 的重量是 wi,其价值为 pi,背包的容量为
M。问应如何装入背包中的物品,使得装人背包中物品的总价值最大?在选择装人
背包的物品时,对每种物品 i 只有两种选择,即装入背包、不装入背包。不能将物
品 i 装人背包多次,也不能只装入部分的物品 i。该问题称为 0-1 背包问题。
0-1 背包问题的符号化表示是,给定 M>0, w i >0, pi >0,1 i n ,要求找
到一个 n 元 0-1 向量向量(x1,x2…xn), X i =0 或 1 , 1 i n, 使得
,而且 达到最大
[2]
。
2.解决方法
2.1 贪心算法
1、贪心算法的基本原理与分析
贪心算法总是作出在当前看来是最好的选择,即贪心算法并不从整体最优解上
加以考虑,它所作出的选择只是在某种意义上的局部最优解。贪心算法不是对所有
问题都能得到整体最优解,但对范围相当广的许多问题它能产生整体最优解。在一
些情况下,即使贪心算法不能得到整体最优解,但其最终结果却是最优解的很好近
似解。
贪心算法求解的问题一般具有两个重要性质:贪心选择性质和最优子结构性质。
所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优解的选择,
�
�
�
�
�
��
�
�
10
i
ii
x
Mwx
p
x
i
i
�
max
�
�
�
�
�
�
Mwx
ii
�
�
p
x
i
i
�
- 3 -
即贪心选择来达到。这是贪心算法可行的第一个基本要素,也是贪心算法与动态规
划算法的主要区别。当一个问题的最优解包含其子问题的最优解时,称此问题具有
最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求
解的关键特征。
2、0-1 背包问题的实现
对于 0-1 背包问题,设 A 是能装入容量为 c 的背包的具有最大价值的物品集合,
则 Aj=A-{j}是 n-1 个物品 1,2,...,j-1,j+1,...,n 可装入容量为 c-wj 的背包的具有最大价
值的物品集合。
用贪心算法求解 0-1 背包问题的步骤是,首先计算每种物品单位重量的价值
vi/wi;然后,将物品进行排序,依贪心选择策略,将尽可能多的单位重量价值最高
的物品装入背包。若将这种物品全部装入背包后,背包内的物品总量未超过 c,则
选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直进行下去,直
到背包装满为止。
2.2 动态规划算法
1、动态规划的基本原理与分析
动态规划算法的基本思想是将待求解问题分解成若干个子问题,先求解子问题,
然后从这些子问题的解得到原问题的解。但是经分解得到的子问题往往不是互相独
立的。不同子问题的数目常常只有多项式量级。如果能够保存已解决的子问题的答
案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式
时间算法。它把已知问题分为很多子问题,按顺序求解子问题,在每一种情况下,
列出各种情况的局部解,按条件从中选取那些最有可能产生最佳的结果舍弃其余。
前一子问题为后面子问题提供信息,而减少计算量,最后一个子问题的解即为问题
解。采用此方法求解 0-1 背包问题的主要步骤如下:
①分析最优解的结构:最有子结构性质;
②建立递归方程;
③计算最优值;
④构造最优解
[4]
。
2、 0-1 背包问题的实现
- 4 -
① 最优子结构性质
0-1 背包问题具有最优子结构性质。设(y1,y2…yn)是所给 0-1 背包问题的一
个最优解,则(y2,y3…yn)是下面相应子问题的一个最优解:
因若不然,设(z2,z3…zn)是上述问题的一个最优解,而(y2,y3…yn)不是它的最优
解,由此可见 ,且 c。因此
c
这说明(y1,z2…zn)是所给 0-1 背包问题的一个更优解,从而(y1,y2…yn)不是所给
0-1 背包问题的最优解。此为矛盾
[1]
。
② 递归关系
设所给 0-1 背包问题的子问题
的最优值为 m(i,j),即 m(i,j)是背包容量为 j,可选择物品为 i,i+1,……,n 时 0-1
背包问题的最优值。由 0-1 背包问题的最优子结构性质,可以建立计算 m(i,j)的递归
式如下:
�
�
n
ik
kk
xvmax
�
�
�
�
�
���
�
�
�
nkix
jxw
k
n
ik
kk
},1,0{
�
�
�
n
i 2
�
�
n
i
ii
yv
2
�
�
�
n
i
ii
zw
2
w1y1
�
��
�
�
n
i
ii
zv
2
v1y1
�
�
n
i
ii
yv
1
�
�
�
n
i
ii
zw
2
w1y1
�
�
�
n
ik
kk
xvmax
�
�
�
�
�
���
�
�
�
nkix
jxw
k
n
ik
kk
},1,0{
�
�
�
���
�����
�
wjjjim
wijviwijimjim
0),,1(
},),1(),),1(max{
j)m(i,
�
�
�
��
�
�
wnj
wnvnj
0
j)m(n,
- 5 -
2.3 回溯法
1、回溯法的基本原理与分析
回溯是一种系统地搜索问题解答的方法。为了实现回溯,首先需要为问题定义一
个解空间,这个解空间必须至少包含问题的一个解(可能是最优的)。回溯法需要为问
题定义一个解空间,这个解空间必须至少包含问题的一个解(可能是最优的)。使用递
归回溯法解决背包问题的优点在于它算法思想简单,而且它能完全遍历搜索空间,
肯定能找到问题的最优解奉但是由于此问题解的总组合数有 个,因此随着物件数
n 的增大,其解的空间将以 n 级增长,当 n 大到一定程度上,用此算法解决背包问
题将是不现实的。
下一步是组织解空间以便它能被容易地搜索。典型的组织方法是图或树。一旦
定义了解空间的组织方法,这个空间即可按照深度优先的方法从开始结点进行搜索,
利用限界函数避免移动到不可能产生解的子空间。
2、 0-1 背包问题的实现
回溯法是一种系统地搜索问题解答的方法。为了实现回溯,首先需要为问题定
义一个解空间,这个解空间必须至少包含问题的一个解(可能是最优的)。一旦定义了
解空间的组织方要选择一个对象的子集,将它们装人背包,以便获得的收益最大,
则解空间应组织成子集树的形状。首先形成一个递归算法,去找到可获得的最大收
益。然后,对该算法加以改进,形成代码。改进后的代码可找到获得最大收益时包
含在背包中的对象的集合。
左子树表示一个可行的结点,无论何时都要移动到它,当右子树可能含有比当
前最优解还优的解时,移动到它。一种决定是否要移动到右子树的简单方法是 r 为
还未遍历的对象的收益之和,将 r 加到 cp (当前节点所获收益)之上,若( r+cp)
bestp(目前最优解的收益),则不需搜索右子树。一种更有效的方法是按收益密度
vi/wi 对剩余对象排序,将对象按密度递减的顺序去填充背包的剩余容量, 当遇到
第一个不能全部放人背包的对象时, 就使用它的一部分。
2.4 分支-限界法
1、分枝-限界法的基本原理与分析
分枝限界发是另一种系统地搜索解空间的方法,它与回溯法的主要区别在于对 E-
n
2
n
2
�
剩余24页未读,继续阅读
资源评论
RDSunday
- 粉丝: 234
- 资源: 204
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功