资源描述：
《计算机算法设计与分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、计算机算法设计与分析0/1背包问题研究报告目录1.问题的定义12.问题的应用背景13.求解0/1背包问题的常用算法23.1遗传算法23.2模拟退火算法33.3蚁群算法33.4贪心算法43.5动态规划法53.6回溯法63.6.1算法描述63.6.2算法设计基本思想63.6.3实例分析73.6.4程序代码及实验结果73.7分支限界法103.7.1算法描述103.7.2算法设计基本思想103.7.3算法求解过程113.7.4分支限界法求解0/1背包问题113.7.5程序代码及实验结果134.常用几种算法比较185.展望190/1背包问题及其
2、求解算法研究背包问题（KnapsackProblem,KP）又称为子集合问题，最早由Dantzing于20世纪50年代提出，是计算机算法中的一类经典问题，也是运筹学中的一类经典的NP完全组合优化问题，在资金分配、货物装载、项目选择等问题上有着广泛的应用。根据物品特性及约束条件的不同，KP问题可分为0/1背包问题和多背包问题两大类，前者又可依据维数的不同，进一步分为一维0/1背包问题、二维0/1背包问题及多维0/1背包问题。本文主要研究简单的0/1背包问题，即一维0/1背包问题。1.问题的定义给定n种重量为wi，价值为pi的物品Wi（i
3、=1,2,...,n）和1个容量为c的背包，问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。在选择装入背包的物品时，对每种物品Wi只有两种选择，即装入背包或不装入背包。不能将物品Wi装入背包多次，也不能只装入部分的物品Wi。因此，该问题称为0/1背包问题。此问题更形式化的描述为：给定c>0，wi>0，pi>0，i=1,2,...,n，要求找出一个n元0/1向量(x1,x2,…,xi,…,xn)，xi{0,1}，i=1,2,...,n，使得，且达到最大。因此，0/1背包问题是一个特殊的整数规划问题，其数学模型表示如下：Ma
4、xs.t.2.问题的应用背景0/1背包问题是当前组合优化领域研究的一个热点和难点问题，其实质就是组合优化问题，即如何在有效的空间内装载更多的物品，实现背包中物品价值的最大化。0/1背包问题是一个特殊的整数规划问题，其最终目标是寻求一种最优的分配策略以获得物品最大的价值量。形象化说，给出一系列可以进行的操作P，每种操作都可以获得相应的价值V，但是进行每一种操作都必须付出相应的代价C，然后求出在总代价不超过给定阈值时可以获取的最大价值。0/1背包问题在现实生活中有着广泛的应用，如下料问题、贷款组合优化问题、项目选择问题等都可以转换为0/1
5、背包问题，即这些问题都可以转换为整数线性规划问题。因此，研究0/1背包问题高效求解算法，无论是在理论上还是在实际应用中都具有一定的价值和意义。191.求解0/1背包问题的常用算法目前，求解0/1背包问题的算法主要有确定性算法和近似算法两大类，确定性算法有分支限界法、动态规划法、回溯法等；近似算法有贪心算法、遗传算法、蚁群算法等。一般来讲，确定性算法只能在短时间内求解小规模的0/1背包问题，而不能快速地求解大规模的0/1背包问题，因此其实用性常常受到问题规模的限制；而近似算法往往只能求解问题的近似解，有时所求得的解的质量不如人意。本节首
6、先对求解0/1背包问题的常用算法进行简要的阐述，然后重点对回溯法和分支限界法求解一维0/1背包问题进行着重分析，并用Java语言在MyEclipse8.0平台下编程实现。3.1遗传算法遗传算法（GeneticAlgorithms,GAs）是由JohnH.Holland及其学生于20世纪60年代末70年代初提出的一种通过模拟生物进化和遗传选择过程来搜索最优解的智能优化方法。基本GAs算法的步骤一般为：确定编码方式及取值范围；初始化染色体的个数，并随机产生所有的染色体；计算个体的适应度；经过遗传算子操作，进行遗传迭代求解。0/1背包问题的
7、遗传算法求解策略如下：将物品Wi按单位重量价值（pi/wi）由大到小排序；依据0/1背包问题的定义（见第1节），则放入背包的总重量为w=，总价值为p=；f[n]存放目标函数值，即个体的适应度，t[n]存放每个个体的约束条件值。(1)产生初始种群，并计算每个个体的适应度值和其对应的约束条件值（即为在染色体中选取的物品的重量），比较初始种群中各个个体的适应度。选择最大者所对应的个体作为第一代最优个体，并记录该个体以及它的适应度和约束条件值；(2)计算每个个体的选择概率；(3)利用轮盘赌法进行个体选择；(4)进行交叉运算，随即选择一对个体产
8、生一对有效交叉位置进行交叉运算，并计算新产生的个体的适应度值和约束条件值。如果新产生的个体重量大于背包容量，则对新产生的个体进行修正，放弃在一个个体中的一个物品，增加另一个个体的一个物品使其重量小于背包重量；(5)进行变
