刘念 911032 01背包问题的算法研究与实现Word文档格式.docx
- 文档编号:7852399
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:27
- 大小:69.40KB
刘念 911032 01背包问题的算法研究与实现Word文档格式.docx
《刘念 911032 01背包问题的算法研究与实现Word文档格式.docx》由会员分享,可在线阅读,更多相关《刘念 911032 01背包问题的算法研究与实现Word文档格式.docx(27页珍藏版)》请在冰点文库上搜索。
内容摘要1
关键词1
Abstract2
Keywords2
1绪论3
1.1问题的提出及研究意义3
1.20-1背包问题的算法研究的分析3
1.3课题的主要研究内容4
20-1背包问题的实现5
2.10-1背包问题在动态规划中的实现5
2.20-1背包问题在回溯法中的实现8
2.30-1背包问题在分枝-限界法中的实现12
2.40-1背包问题在遗传算法中的实现16
3解0-1背包问题的算法比较与分析20
4总结与展望22
参考文献23
致谢25
内容摘要:
背包问题是一个在运筹学领域里常见的典型NP-C难题,也是算法设计分析中的经典问题,对该问题的求解方法的研究无论是在理论上,还是在实践中都具有重要意义。
对这个问题的求解已经研究出了不少的经典方法,对该问题的探索和应用研究一直在进行。
在先进理论指导下,求解0-1背包问题具有科学、高效、经济、灵活、方便等显著特点。
那么要解决背包问题,首要的前提就是设计出好的算法,想求得背包问题的解,就要先设计出算法,本文采用动态规划法,回溯法,分枝-限界法,遗传算法四种方法分别对背包问题、0-1背包问题及简单0-1背包问题进行算法设计和时间复杂度分析,给出具体算法设计和实现过程。
并以具体实例详细描述不同方法求解问题解时算法基本思想,然后就解决0-1背包问题对这四种算法进行详细的比较,总结四种方法实现的优缺点并得出结论。
如何将背包问题应用于实际问题中,有针对性地设计适合求解实际0-1背包问题的算法,并很好地解决实际问题,是计算机工作者不断思索、研究的一个领域。
关键词:
0-1背包动态规划回溯法分枝-限界法遗传算法
Abstract:
KnapsackproblemisatypicalNP-Cproblemaswellasalgorithmdesignandanalysisoftheclassicalproblemsinthecommonfieldofoperationsresearch.Itisveryimportanttostudythesolutionoftheproblem,whetherintheoryorinpractice.Aftersomeresearch,alotofclassicalmethodssolvingthisproblemhavebeencomeupwith,andtheexplorationofthisissueandappliedresearchhasbeenongoing.Undertheguidanceofadvancedtheory,therearedistinctivefeaturessuchasscientific,efficient,economic,flexibleandconvenientfeaturesinsolvingthe0-1knapsackproblem.
Sotosolvetheknapsackproblem,thefirstpremiseistodesignagoodalgorithm.Toseekthesolutionofknapsackproblem,itisnecessarytodesignalgorithmsusingdynamicprogrammingatfirst.Inthispaper,fourmethodssuchasdynamicprogramming,backtracking,branch-Boundmethodandgeneticalgorithmrespectivelyaimingatknapsackproblem,0-1knapsackproblemandasimple0-1knapsackproblemcarryoutthealgorithmdesignandanalysisoftimecomplexity,andgivethespecificalgorithmdesignandimplementationoftheprocess.Anddescriptdetailedlythebasicideaofalgorithmbyusingspecificexamplesinsolvingtheissuewithdifferentways.Andthenaimingatsolvingthe0-1knapsackproblem,comparefouralgorithmsindetailandsummarizetheadvantagesanddisadvantagesofrealizationoffourmethodsandreachaconclusion.Howtoapplytheknapsackproblemintothepractical,andtodesigntargetedforthepracticalalgorithmsofsolving0-1KnapsackProblemandtosolvethepracticalproblemsverywell,isanareaofcomputerworkers’constantlythinkingandstudy.
Keywords:
0-1knapsackproblemdynamicprogrammibacktrackingbranch-Boundmethodgeneticalgorithm
1绪论
1.1问题的提出及研究意义
0-1背包问题是计算机科学中的一个非常经典的优化问题。
也是被证明了的NP难度问题。
它是在1978年由Merkel和Hellman提出的。
它的主要思路是假定某人拥有大量物品,重量各不同。
此人通过秘密地选择一部分物品并将它们放到背包中来加密消息。
背包中的物品中重量是公开的,所有可能选择的物品也是公开的,但背包中的物品是保密的。
附加一定的限制条件,给出重量,而要列出可能的物品,在计算上是不可实现的。
背包问题是熟知的不可计算问题,背包体制以其加密,解密速度快而其人注目。
但是,大多数一次背包体制均被破译了,因此现在很少有人使用它。
围绕这个问题的求解方法很多,比如贪婪算法、动态规划、分枝限界、回溯法、遗传算法等等。
其中回溯法是常见的一种求解方法。
多年来,背包问题吸引了许多理论和实际工作者对此问题作深入的研究,在理论上,尽管背包问题的结构简单,但它却具有组合爆炸的性质,在实际应用中,许多工业问题都可以用背包问题来描述求解,如资金运算、货舱装载、存储分配等都是其典型的应用例子。
如何将背包问题应用于实际问题中,并很好地解决实际问题,是计算机工作者不断思索、研究的一个领域。
1.20-1背包问题的算法研究的分析
0-1背包问题的算法研究主要是通过算法设计与分析知识,设计解决相关问题的尽可能高效的算法并程序实现,而且能够分析算法的复杂性,通过实验进一步领会各种算法设计技术的基本原理,掌握算法设计和分析方法,提高算法设计与分析的应用能力。
0-1背包是一类很典型的优化问题,研究它有很重要的实际意义,这不仅是由于它结构简洁,可以作为子问题为研究更复杂的问题奠定理论基础,有很高的理论研究价值,而且由于它是许多实际工程应用问题的种通用化描述,在很多实际问题当中有着非常广泛的应用背景,例如项目决策等。
他是最基本的背包问题,即对一个物体要么选用,要么就抛弃,不能将一个物体再继续细分的情况。
它包含了背包问题中设计状态、方程的最基本思想,在经济管理、资源分配、投资决策、装载设计等领域有着重要的应用价值。
在计算理论中属于NP-C完全问题,其计算复杂度,传统上采用动态规划来求解。
背包问题就是在资源有限的条件下,追求总的最大收益的资源有效分配问题。
1.3课题的主要研究内容
1.3.1背包问题的描述
背包问题是整数规划中的一类特殊问题,在现实生活中具有广泛应用。
如果能提出求解此问题的有效算法,则具有很好的经济价值和决策价值。
问题的一般描述是:
旅行者背包登山,背包的最大承重为M,现有n个物品可供选择装入背包,第i个物品莺量为wi,价值为pi,假定物品i的一部分xi(0
xi
1)放人背包,获得价值为xipi,由于背包最大承重为M,要求装入物品总质量不过超过M,问旅行者应该如何选择物品装入背包,使得装入物品的价值总和达到最大值。
背包问题的数学描述如下:
要求找到一个n元向量(x1,x2…xn),在满足约束条件:
情况下,使得目标函数
,其中,1
i
n;
M>
0;
wi>
pi>
0。
满足约束条件的任何向量都是一个可行解,而使得目标函数达到最大的那个可行解则为最优解[1]。
1.3.20-1背包问题
①0-1背包问题的提出
给定n种物品和1个背包。
物品i的重量是wi,其价值为pi,背包的容量为M。
问应如何装入背包中的物品,使得装人背包中物品的总价值最大?
在选择装人背包的物品时,对每种物品i只有两种选择,即装入背包、不装入背包。
不能将物品i装人背包多次,也不能只装入部分的物品i。
该问题称为0-1背包问题。
②问题符号化
0-1背包问题的符号化表示是,给定M>
0,wi>
0,pi>
0,1
n,要求找到一个n元0-1向量向量(x1,x2…xn),Xi=0或1,1
n,使得
,而且
达到最大[2]。
20-1背包问题的实现
2.10-1背包问题在动态规划中的实现
2.1.1动态规划的基本原理与分析
动态规划算法的基本思想是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。
但是经分解得到的子问题往往不是互相独立的。
不同子问题的数目常常只有多项式量级。
如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法。
它把已知问题分为很多子问题,按顺序求解子问题,在每一种情况下,列出各种情况的局部解,按条件从中选取那些最有可能产生最佳的结果舍弃其余。
前一子问题为后面子问题提供信息,而减少计算量,最后一个子问题的解即为问题解。
采用此方法求解0-1背包问题的主要步骤如下:
①分析最优解的结构:
最有子结构性质;
②建立递归方程;
③计算最优值;
④构造最优解[4]。
动态规划算法的每一步决策都是根据前一步的状态参量来决定这一步状态参量的设置,也就是说,从初始状态到最终状态要经过多个过程,经历不同的状态,不断地根据上一步状态决定下一状态,从而形成了一个决策序列,最终将整个问题解决,这就是典型的多段决策的特性。
由上面的动态规划法的介绍,可以看出0-1背包问题,是符合多段决策的特点和具有重叠子问题。
因此,在设计0-1背包问题解决方案时,可以将整个物品放到背包的过程,看成一个取物品的过程。
2.2.20-1背包问题的实现
①最优子结构性质
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)的递归式如下:
③算法描述
基于以上讨论,当wi(1
n)为正整数时,用二维数组m[][]来存储m(i,j)的相应值,可设计解0-1背包问题的动态规划算法Knapsack入下:
template<
classType>
voidKnapsack(Typev,intw,intc,intn,Type**m)
{
intjMax=min(w[n]-1,c);
for(intj=0;
j<
=jMax;
j++)m[n][j]=0;
for(intj=w[n];
=c;
j++)m[n][j]=v[n];
for(inti=n-1;
i>
1;
i--){
jMax=min(w[i]-1,c);
j++)m[i][j]=m[i+1][j];
for(intj=w[i];
j++)m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
}
m[1][c]=m[2][c];
if(c>
=w[1])m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);
}
voidTraceback(Type**m,intw,intc,intn,intx)
for(inti=1;
i<
=n;
i++)
if(m[i][c]==m[i+1][c])x[i]=0;
else{x[i]=1;
c-=w[i];
x[n]=(m[n][c])?
1:
0;
}[1]
④计算复杂性分析
利用动态规划求解0-1背包问题的复杂度为0(min{nc,2n}。
动态规划主要是求解最优决策序列,当最优决策序列中包含最优决策子序列时,可建立动态规划递归方程,它可以帮助高效地解决问题[8]。
2.20-1背包问题在回溯法中的实现
2.2.1回溯法的基本原理与分析
回溯是一种系统地搜索问题解答的方法。
为了实现回溯,首先需要为问题定义一个解空间,这个解空间必须至少包含问题的一个解(可能是最优的)。
回溯法需要为问题定义一个解空间,这个解空间必须至少包含问题的一个解(可能是最优的)。
使用递归回溯法解决背包问题的优点在于它算法思想简单,而且它能完全遍历搜索空间,肯定能找到问题的最优解奉但是由于此问题解的总组合数有
个,因此随着物件数n的增大,其解的空间将以
n
级增长,当n大到一定程度上,用此算法解决背包问题将是不现实的。
下一步是组织解空间以便它能被容易地搜索。
典型的组织方法是图或树。
一旦定义了解空间的组织方法,这个空间即可按照深度优先的方法从开始结点进行搜索,利用限界函数避免移动到不可能产生解的子空间。
①回溯法的算法描述
回溯法是一种系统地搜索问题解答的方法。
一旦定义了解空间的组织方要选择一个对象的子集,将它们装人背包,以便获得的收益最大,则解空间应组织成子集树的形状。
首先形成一个递归算法,去找到可获得的最大收益。
然后,对该算法加以改进,形成代码。
改进后的代码可找到获得最大收益时包含在背包中的对象的集合。
左子树表示一个可行的结点,无论何时都要移动到它,当右子树可能含有比当前最优解还优的解时,移动到它。
一种决定是否要移动到右子树的简单方法是r为还未遍历的对象的收益之和,将r加到cp(当前节点所获收益)之上,若(r+cp)
bestp(目前最优解的收益),则不需搜索右子树。
一种更有效的方法是按收益密度vi/wi对剩余对象排序,将对象按密度递减的顺序去填充背包的剩余容量,当遇到第一个不能全部放人背包的对象时,就使用它的一部分。
②解0-1背包问题的回溯算法描述如下:
classTypew,classTypep>
classKnap{
friendTypepKnapsack(Typep*,Typew*,Typew,int);
private:
TypepBound(inti);
voidBacktrack(inti);
Typewc;
//背包容量
intn;
//物品数
Typew*w;
//物品重量数组
Typep*p;
//物品价值数组
Typewcw;
//当前重量
Typepcp;
//当前价值
Typepbestp;
//当前最优价值
};
voidknap<
Typew,Typep>
:
Backtrack(inti)
if(i>
n){//到达叶结点
bestp=cp;
return;
if(cw+w[i]<
=c){//进入左子数
cw+=w[i];
cp+=p[i];
Backtrack(i+1);
cw-=w[i];
cp-=p[i];
if(Bound(i+1)>
bestp)//进入右子数
TypepKnap<
Bound(inti)
{//计算上界
Typewcleft=c-cw;
//剩余容量
Typepb=cp;
//以物品单位重量价值递减序装入物品
while(i<
=n&
&
w[i]<
=cleft){
cleft-=w[i];
b+=p[i];
i++;
}
//装满背包
if(i<
=n)b+=p[i]*cleft/w[i];
returnb;
classObject{
friendintKnapsack(int*,int*,int,int);
public;
intoperator<
=(Objecta)const
{return(d>
=a.d);
private:
intID;
floatd;
TypepKnapsack(Typepp[],Typepw[],Typewc,intn)
//为Knap:
Backtrack初始化
TypewW=0;
TypepP=0;
Object*Q=newObject[n];
for(inti=1;
i++){
Q[i-1].ID=i;
Q[i-1].d=1.0*p[i]/w[i];
p+=p[i];
w+=w[i];
if(w<
=c)returnP;
//装入所有物品
//依物品单位重量价值排序
sort(Q,n);
Knap<
K;
K.p=newTypep[n+1];
K.w=newTypew[n+1];
K.p[i]=p[Q[i-1].ID];
K.w[i]=w[Q[i-1].ID];
K.cp=0;
K.cw=0;
K.c=c;
K.n=n;
K.bestp=0;
//回搠搜索
K.Backtrack
(1);
delete[]Q;
delete[]K.w;
delete[]K.p;
retureK,bestp;
③算法效率
由于计算上界函数需要O(n)时间,在最坏情况下有O(
)个右孩子结点需要上界函数,故计算0-1背包问题的回溯算法所需的计算时间复杂度为O(n
)。
对回溯法的改进主要是对判断是否移动右子树上,一种更有效的方法是按效益密度vi/wi对剩余对象排序,将对象按密度递减的顺序去填充背包的剩余容量,当遇到第一个不能全部放人背包的对象时,就使用它的一部分。
回溯算法的运行时间取决于它在搜索过程中所生成的结点数,而限界函数可以大量减少所生成的结点个数,省去许多无谓的搜索,使得搜索速度更快,其调用限界函数计算上界需花费O(n)时间,最坏情况下有O(
)个结点需调用限界函数,需花费O(n)时间,所以该算法的时间复杂度为O(n
)[12]。
回溯法的另一个重要特性就是在搜索执行的同时产生解空间在搜索期间的任何时刻仅保留从开始结点到当前可扩展结点的路径其空间需求为O(从开始结点起最长路径的长度),所以,此处该算法的空间复杂度为O(n),回溯法是算法设计的基本方法之一,它适用于解一些涉及到寻找一组解的问题或者求满足某些约束条件的最优解的问题,且适用于求解组合数量较大的问题。
2.30-1背包问题在分枝-限界法中的实现
2.3.1分枝-限界法的基本原理与分析
分枝限界发是另一种系统地搜索解空间的方法,它与回溯法的主要区别在于对E-结点(expansionnode)的扩充方式。
每个活结点有且仅有一次会变成E-结点。
当一个结点变为E-结点时,则生成从该结点移动一步即可到达的所有新结点。
在生成的结点中,抛弃那些不可能导出(最优)可行解的结点,其余结点加人活结点表,然后从表中选择一个结点作为下一个E结点。
从活结点表中取出所选择的结点并进行扩充,直到找到解或活动表为空,扩充才结束。
有两种常用的方法可用来选择下一个E-结点:
①先进先出(FIFO)即从活结点表中取出结点的顺序与加人结点的顺序相同,因此活结点表的性质与队列相同。
②最小耗费或最大收益法在这种模式中,每个结点都有一个对应的耗费或收益。
如果查找一个具有最小耗费的解,则活结点表可以最小堆来建立,下一个E-结点就是具有最小耗费的活结点,如果希望搜索一个具有最大收益的解,则可用最大堆来构造活结点表,下一个E-结点是具有最大收益的活结点[15]。
2.3.20-1背包问题的实现
工作在解空间树上的FIFO分枝定界方法非常
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 刘念 911032 01背包问题的算法研究与实现 01 背包 问题 算法 研究 实现