0-1背包问题的算法与研究 优化作业
0-1背包问题算法分析
背包问题又称子集合问题,最早是由Dantzing 于20世纪50年代首次提出的,已成为计算机学科中一个经典的NP 问题 . 0－1背包问题在很多领域都有广泛的应用,很多实际问题都可转换为0－1背包问题，例如下料问题,贷款组合优化决策问题等，0－l 整数线性规划问题可以归结为0－1背包问题,而整数线性规划问题都可以转化为0－l 整数线性规划问题。所以,对0－1背包问题求解方法的研究无论是在理论上还是在实践中都具有一定的意义。
一 0－1 背包问题的数学模型及其分类
0－1 背包问题的数学模型如下：
假设n 个物件,其重量用w i 表示,价值为p i （i ＝1，2，…， n ），背包的最大容纳重量为c,当物件i 被选入背包时,定义变量 x i ＝1，否则 x i ＝0。现在考虑 n 个物件的选择与否,则背包内 n 个物件总重量为Σw i x i ，物件的总价值为Σp i x i ，如何决定变量x i （i ＝1，2，…，n ）的值（即确定一个物件组合）使背包内物件总价值为最大，其数学模型表示如下：
{ 0
..max 11≤∑∑==i n i i i n i i x w t s x p
到目前为止，求解0－1背包问题的方法很多,精确算法有分支限界法,动态规划法等,近似算法有贪婪方法、蚁群算法等。一般来说，精确算法不能在较短时间内求解大规模0－1背包问题,使其实用性受到限制。 而近似算法只能求解问题的近似解，有时所得的近似解质量很低。本文主要针对常见的求解0－1背包问题的算法设计方法进行阐述.
二 算法思想描述及其性能分析
1 分支界限法
第一个基于分支界限法的背包问题求解是由Horowit znd Sahni,Nauss and Martello and Toth 于20世纪70年代提出.分支界限法的基本思想是对有约束条件的最优化问题的所有可行解(数目有限)空间进行搜索.该算法在具体执行时,把全部可行的解空间不断分割为越来越小的子集(成为分支),并为每个子集内的解的值计算一个下界或上界(称为定界).在每次分支后,对凡是界限超出已知可行解值的那些子集不再做进一步分支.这样,解的许多子集(即搜索树上的许多结点)就可以不予考虑了,从而缩小了搜索范围.这一过程一直进行到找出可行解为止,该可行解的值不大于任何子集的界限,因此这种算法一般可以求得最优解.
分支界限法是组合优化问题的有效求解方法,对于0－1背包问题,其计算步骤如下所述:
(1) 计算每个节点即解集中部分物品的重量和。如当前重量超过背包容量w ，
则将在该节点下的所有子树删除；
(2) 计算上一级分支的所有可能解的价值，如果当前分支的价值比较小或相
等则删除。
分支界限法并不用于纯粹的深度优先模式，而是最好优先：选择最优希望达到目标结点的结点优先扩展。此算法由于从最小下界分支，每次算完限界后，把搜索树上当前所有的叶子结点的界限进行比较，找出限界最小的结点，此结点即为下次分支的结点。这种决策的优点是检查子问题较少，能较快地求得最佳解。
在最坏情况下，不可避免地要在整个状态空间树上进行搜索，要存储很多叶子结点的限界和对应的耗费矩阵，需要数级的时间复杂度O （n
2），此时其空间消耗也较大。可以说一个分支定界求解方法的效率基本上由值界方法决定，若界估计不好，在极端情况下将于穷举搜索没多大区别。
2 动态规划法
动态规划法DM （Dynamic Programming ，简称DM ）是美国 数学家
Bellman R E 等人20世纪50年代初在研究阶段决策过程的优化问题时提出的，把多阶段决策过程转化为一系列单阶段决策问题逐个求解，创立了解决这类过程优化问题的新方法—动态规划。动态规划算法是先把问题分成多个子问题（一般地每个子问题是互相关联和影响的），再依次研究逐个问题的决策。决策就是某个阶段的状态确定后，从该状态演变到下一阶段状态的选择。 当全体子问题都解决时，整体问题也随之解决。用枚举的方法从所有可能的决策序列中去选取最优决策序列可能是较费时的笨拙方法，但利用最优性原理去找出递推关系，再找最优决策序列就可能使得枚举数量大大下降，这就是动态规划方法设计算法的主要思路。
设F k （y ）为背包只装前k 种东西，总重限制为y 的情况下所具有的最大价值，即 )0()
0(max )(11b y y x
w n k x p y F i k i i i k
i i k ≤≤≤≤≤=∑∑==
这两个式子分别为背包问题子问题的目标函数和约束条件，不难看出是满足优化原则的。使用动态规划法求解，所得递推公式和边界条件是：
F k （y ）＝max （F k －1（y ），F （y －w k ）＋p k ），
F 0（y ）＝0，对一切 y ，0≤y ≤c ， F k （y ）＝0，对一切 y ，0≤k ≤n ， F 1（y ）＝[y/w 1]·p 1
用动态规划方法求解 0－1 背包问题的过程如下：①将问题分解为若干个子问题（一般每个子问题是相互关联和影响的 ），再依次研究逐个问题的决策，也就是把整个问题的最优解与子 问题的局部最优解用递推等式联系起来；②定义边界条件；③把边界条件代入递推公式，逐步求得最优解。
动态规划算法是一种经典的背包问题求解算法，其原理简单，算法思路清晰易于实现。动态规划算法虽然高效，但是对于规模较大的问题它并不是一个理想
的算法，最重要的原因就是它的维数障碍，即计算和存储量的需要对于状态空间和决策空间的维数的增长呈指数增长关系。这样惊人的增长速度是计算机难以承受的，这就使得直接的动态规划方法求解规划较大的背包问题发生了困难，且目前尚没有好的解决办法。
3 蚁群算法
蚁群算法由意大利学者 Dorigo 等人首先提出，是模仿真实的蚁群行为而提出的一种模拟进化算法。蚂蚁之间是通过一种称为信息 素（Pheromone ）的物质传递信息的，蚂蚁能够在经过的路径上留下该种物质，而且能够感知这种物质的存在及其强度，并以此来指导自己的运动方向。因此，由大量蚂蚁组成的集体行为便表现出一种信息正反馈现象：某一条路径上走过的蚂蚁越多，该路径上留下的信息素就越多，则后来者选择该路径的概率就越大。蚂蚁之间就是通过这种信息素的交流，搜索到一条从蚁巢到食物源的最短路径。将这一问题的核心运用到背包问题中：在某一物品上聚集的信息素越多，则该物品被选择的概率就越大。就蚁群算法而言，当处理的数据比较小时，其具有很快的收敛速度 ，而随着数据规模的增大，算法的收敛速度明显降低。
假设有m 只蚂蚁，n ＋1个城市，第o 个城市代表背包，第1～n 个城市代表各个物品。把第o 个城市看成蚂蚁的寻优起点。令 n ij ＝p i ／ w i 表示蚂蚁从城市转移到城市的期望程度，这样价值越高同时重量越小的物品对蚂蚁的吸引就越大 。令 e ij 表示路径中留下的信息素强度。 任一只蚂蚁 k 由城市 i 转移到城市j 的概率可设为：
),2,1,0(1n j i n e n e p n j b ij
a ij
b ij a ij k ij ===
∑= 其中α表示路径上的信息量对蚂蚁选择路径所起的作用大小，β 为吸引度的重要性。每只蚂蚁从寻优起点出发只需一步就可到达 1～n 当中任意一个食物源，所以上式中有 （i ＝1，2，…，n ）。寻优过程由多只蚂蚁进行，当每只蚂蚁以较大的概率选中食物源 j 时，如果有c －Σw i x i ≥0，则变量xj 将加1，否则给从i 到 j 的路径以罚值，以使后续的蚂蚁不再选择本路径。当所有节点都受罚以后将结束一次求解过程。然后记录最优解，更新信息素。 更新的公式可为
Δe ij ＝Q*w j *x j
e ij （t ＋1）＝（1－ρ）*e ij （t ）＋Δe ij （i ＝0，j ＝1，2，…，n ）
上式 中 ρ 为挥发系数，Q 为正常数，x j 为经过该路径的蚂蚁数量。
用蚁群算法求解 0－1 背包问题的过程如下：①初始化：即将任意两个城市之间的道路上的信息素赋一个初值；②搜索：让若干只蚂蚁根据信息素和距离选择城市；③每到一个新城市，进行信息素局部更新；④所有蚂蚁完成回路后，进行全局信息素更新；⑤记录最优路径，返回步骤②循环直到满足退出条件。
蚁群算法是近年来发展起来的一种随机算法，已经证明可以有效解决背包问题。但是蚁群算法的收敛性证明尚处于初步阶段，缺乏完善的理论基础。并且在减少寻优计算量和缩短算法运行时间方面,有待进一步改进。
4 贪婪法
贪婪算法通过一系列的选择得到问题的解,在每一次总是做出在当前状态下看来是最好的选择，也就是希望通过局部的最优来达到一个全局的最优。这种启发式的策略并不总能获得最优解，然而在许多情况下确能达到预期的目的，而且对于很多N－P问题来说,本身就不存在最优解。
对于0－1背包问题来说，贪婪的策略有常用的3种。每种贪婪策略都采用多步过程来完成背包的装入。在每一步过程中利用贪婪准则选择一个物品装入背包。
第一种贪婪准则:从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。
第二种贪婪准则：从剩下的物品中选择可装入背包的重量最小的物品，如此继续下去直到不能满足条件为止。
第三种贪婪准则：价值密度（价值重量比p i／w i）贪婪算法，这种选择准则为：从剩余物品中选择可装入包的p i／w i值最大的物品，这也是本文所选择的贪婪策略，因为它是一个直觉上近似的解。
用贪婪算法求解0－1背包问题的过程如下：①对于给定的物品，分别求出价值密度（价值重量比），r i＝p i／w i，i＝1，2，…，n；②忽略先前的物品排序，按照价值密度，进行非升序排列：（p（1）/w（1）≥（p（2）/w （2）≥…≥（p（n）/w (n））；
③重复以下步骤，直到不满足条件为止：对于当前的物品，如果重量小于包中剩余的容量，则放入并置物品标志为1（表明被选中），否则就停止。
算法主要耗时是在于将各种物品按价值密度大小排序，本文利用MATLAB软件中的SORTROWS函数进行排序，此函数是基于快速排序（quicksort）实现的，因此算法的时间复杂度为O（nlogn）。
其他算法和各种算法的改进
除了以上介绍的算法外，还有DNA算法，人工神经网络，递归，回溯法，克隆选择算法，禁忌搜索与GA算法，混合算法等，由于各种算法都有自身的优点和不足，许多学者通过利用一种算法的有点同时通过结合其他算法避免该算法的不足，出现了混合算法，这些算法都取得了很大成功。
通过计算复杂度的研究表明0－1背包问题是一个经典的NP问题。对于规模过大的0－1背包问题，人们还是无法找到完美的求解方法，所有智能算法都是在一定范围内求解。许多算法有其局限性，例如只能解决特定的0－1背包问题，但用于其0－1背包问题时求解结果不一定好。
0－1 背包问题未来的发展趋势：①对现有算法开展理论上的研究，寻求算法在理论上的解释和证明，通过加深对算法理论的认识，从而对算法进行改进和完善，得到更优解；②继续研究结合多种算法的混合优化算法；③通过其它学科的算法得到启发，提出新的算法，继而推动0－1 背包问题的研究。
01背包问题不同算法设计、分析与对比报告
实验三01背包问题不同算法设计、分析与对比一．问题描述 给定n种物品和一背包。物品i的重量是w i ，其价值为v i ，背包的容量为c。 问题：应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。 说明：在选择装入背包的物品时，对每种物品i只有两个选择，装入背包或不装入背包，也不能将物品装入背包多次。 二．实验内容与要求 实验内容： 1.分析该问题适合采用哪些算法求解（包括近似解）。 ^ 动态规划、贪心、回溯和分支限界算法。 2.分别给出不同算法求解该问题的思想与算法设计，并进行算法复杂性分析。 动态规划： 递推方程： m(i,j) = max{m(i-1,j),m(i-1,j-wi)+vi} j >= wi; m(i-1,j) j < wi; 时间复杂度为O(n). 贪心法： ^ 算法思想：贪心原则为单位价值最大且重量最小，不超过背包最大承重量为约束条件。也就是说，存在单位重量价值相等的两个包，则选取重量较小的那个背包。但是，贪心法当在只有在解决物品可以分割的背包问题时是正确的。贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。 用贪心法设计算法的特点是一步一步地进行，根据某个优化测度（可能是目标函数，也可能不是目标函数），每一步上都要保证能获得局部最优解。每一步只考虑一个数据，它的选取应满足局部优化条件。若下一个数据与部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中， 直到把所有数据枚举完，或者不能再添加为止。 回溯法：
回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。这种具有限界函数的深度优先生成法称为回溯法。 对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1向量组成,可用子集数表示。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入左子树。当右子树中有可能包含最优解时就进入右子树搜索。 时间复杂度为：O(2n) 空间复杂度为：O(n) ： 分支限界算法： 首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。在优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。 算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。 3.设计并实现所设计的算法。 4.对比不同算法求解该问题的优劣。 这动态规划算法和贪心算法是用来分别解决不同类型的背包问题的，当一件背包物品可以分割的时候，使用贪心算法，按物品的单位体积的价值排序，从大到小取即可。当一件背包物品不可分割的时候，（因为不可分割，所以就算按物品的单位体积的价值大的先取也不一定是最优解）此时使用贪心是不对的，应使用动态规划。 5.需要提交不同算法的实现代码和总结报告。 动态规划方法： public class Knapsack {
算法设计背包问题
算法实验报告 ---背包问题 实验目的 1．掌握动态规划算法的基本思想，包括最优子结构性质和基于表格的最优 值计算方法。 2．熟练掌握分阶段的和递推的最优子结构分析方法。 3．学会利用动态规划算法解决实际问题。 问题描述： 给定n种物品和一个背包。物品i的重量是wi，体积是bi，其价值为vi， 背包的容量为c，容积为d。问应如何选择装入背包中的物品，使得装入背包中 物品的总价值最大? 在选择装入背包的物品时，对每种物品只有两个选择：装入 或不装入，且不能重复装入。输入数据的第一行分别为：背包的容量c，背包的 容积d，物品的个数n。接下来的n行表示n个物品的重量、体积和价值。输出 为最大的总价值。 问题分析: 标准0-1背包问题，MaxV表示前i个物品装入容量为j的背包中时所能产生的最大价值，结构体objec表示每一个可装入物品，其中w表示物品的重量，v表示物品的价值。如果某物品超过了背包的容量，则该物品一定不能放入背包，问题就变成了剩余i-1个物品装入容量为j的背包中所能产生的最大价值；如果该物品能装入背包，问题就变成i-1个物品装入容量为j-objec[i].w的背包所能产生的最大价值加上物品i的价值objec[i].v. 复杂性分析 时间复杂度，最好情况下为0，最坏情况下为：（abc） 源程序 #include
北航最优化方法大作业参考
北航最优化方法大作业参考
1 流量工程问题 1.1 问题重述 定义一个有向网络G=(N,E)，其中N是节点集，E是弧集。令A是网络G的点弧关联矩阵，即N×E阶矩阵，且第l列与弧里(I,j)对应，仅第i行元素为1，第j行元素为-1，其余元素为0。再令b m=(b m1,…,b mN)T，f m=(f m1,…,f mE)T，则可将等式约束表示成： Af m=b m 本算例为一经典TE算例。算例网络有7个节点和13条弧，每条弧的容量是5个单位。此外有四个需求量均为4个单位的源一目的对，具体的源节点、目的节点信息如图所示。这里为了简单，省区了未用到的弧。此外，弧上的数字表示弧的编号。此时，c=((5,5…,5)1 )T， ×13 根据上述四个约束条件，分别求得四个情况下的最优决策变量x=((x12,x13,…,x75)1× )。 13 图 1 网络拓扑和流量需求
1.2 7节点算例求解 1.2.1 算例1（b1=[4;-4;0;0;0;0;0]T） 转化为线性规划问题： Minimize c T x1 Subject to Ax1=b1 x1>=0 利用Matlab编写对偶单纯形法程序，可求得: 最优解为x1*=[4 0 0 0 0 0 0 0 0 0 0 0 0]T 对应的最优值c T x1=20 1.2.2 算例2（b2=[4;0;-4;0;0;0;0]T） Minimize c T x2 Subject to Ax2=b2 X2>=0 利用Matlab编写对偶单纯形法程序，可求得: 最优解为x2*=[0 4 0 0 0 0 0 0 0 0 0 0 0]T 对应的最优值c T x2=20 1.2.3 算例3（b3=[0;-4;4;0;0;0;0]T） Minimize c T x3 Subject to Ax3=b3 X3>=0 利用Matlab编写对偶单纯形法程序，可求得: 最优解为x3*=[4 0 0 0 4 0 0 0 0 0 0 0 0]T 对应的最优值c T x3=40
动态规划之01背包问题(最易理解的讲解)
01背包问题，是用来介绍动态规划算法最经典的例子，网上关于01背包问题的讲解也很多，我写这篇文章力争做到用最简单的方式，最少的公式把01背包问题讲解透彻。 01背包的状态转换方程f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ), f[i-1,j] } f[i,j]表示在前i件物品中选择若干件放在承重为j 的背包中，可以取得的最大价值。 Pi表示第i件物品的价值。 决策：为了背包中物品总价值最大化，第i件物品应该放入背包中吗？ 题目描述： 有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最 首先要明确这张表是从右到左,至底向上生成的。 为了叙述方便，用e10单元格表示e行10列的单元格，这个单元格的意义是用来表示只有物品e时，有个承重为10的背包，那么这个背包的最大价值是6，因为e物品的重量是4，背包装的了，把e装进去后价值为6。然后是e9单元格表示背包承重9，只有物品e, e装进去后，背包价值为6，接着是e8, e7单元格，一直到e3单元格表示背包承重3，但物品e承重4，装不了，所以e3=0, 对于d10单元格，表示只有物品e，d时,承重为10的背包,所能装入的最大价值，是10，因为物品e,d这个背包都能装进去。对于承重为9的背包，d9=10,是怎么得出的呢？ 根据01背包的状态转换方程，需要考察两个值， 一个是f[i-1,j],对于这个例子来说就是e9的值6，另一个是f[i-1,j-Wi]+Pi； 在这里， f[i-1,j]表示我有一个承重为9的背包，当只有物品e可选时，这个背包能装入的最大价值 f[i-1,j-Wi]表示我有一个承重为4的背包（等于当前背包承重减去物品d的重量），当只有物品e可选时，这个背包能装入的最大价值 f[i-1,j-Wi]就是指单元格e4值为6，Pi指的是d物品的价值，即4 由于f[i-1,j-Wi]+Pi = 6 + 4 = 10 大于f[i-1,j] = 6，所以物品d应该放入承重为9的背包，所以d9=10.
解0-1背包问题的动态规划算法
关于求解0/1背包问题的动态规划算法 摘要：本文通过研究动态规划原理，提出了根据该原理解决０／１背包问题的方法与算法实现， 并对算法的正确性作了验证．观察程序运行结果，发现基于动态规划的算法能够得到正确的决策方案且比穷举法有效． 关键字：动态规划；０／１背包；约束条件；序偶；决策序列；支配规则 1、引 言 科学研究与工程实践中，常常会遇到许多优化问题，而有这么一类问题，它们的活动过程可以分为若干个阶段，但整个过程受到某一条件的限制。这若干个阶段的不同决策的组合就构成一个完整的决策。0/1背包问题就是一个典型的在资源有限的条件下，追求总的收益最大的资源有效分配的优化问题。 对于0/1背包问题，我们可以这样描述：设有一确定容量为C 的包及两个向量C ’=（S 1，S 2，……，S n ）和P=（P 1，P 2，……，P N ），再设X 为一整数集合，即X=1，2，3，……，N ，X 为SI 、PI 的下标集，T 为X 的子集，那么问题就是找出满足约束条件∑S i 〈=C ，使∑PI 获得最大的子集T 。在实际运用中，S 的元素可以是N 个经营项目各自所消耗的资源，C 可以是所能提供的资源总量，P 的元素可是人们从各项项目中得到的利润。 0/1背包问题是工程问题的典型概括，怎么样高效求出最优决策，是人们关心的问题。 2、求解问题的动态规划原理与算法 2．1动态规划原理的描述 求解问题的动态规划有向前处理法向后处理法两种，这里使用向前处理法求解0/1背包问题。对于0/1背包问题，可以通过作出变量X 1，X 2，……，X N 的一个决策序列来得到它的解。而对于变量X 的决策就是决定它是取0值还是取1值。假定决策这些X 的次序为X n ，X N-1，……，X 0。在对X 0做出决策之后，问题处于下列两种状态之一：包的剩余容量是M ，没任何效益；剩余容量是M-w ，效益值增长了P 。显然，之后对X n-1，Xn-2，……，X 1的决策相对于决策X 所产生的问题状态应该是最优的，否则X n ，……，X 1就不可能是最优决策序列。如果设F j （X ）是KNAP （1，j ，X ）最优解的值，那么F n （M ）就可表示为 F N （M ）=max(f n (M),f n-1(M-w n )+p n )} （1） 对于任意的f i (X),这里i>0，则有 f i (X)=max{f i-1(X),f i-1(X-w i )+p i } （2） 为了能由前向后推而最后求解出F N （M ），需从F 0（X ）开始。对于所有的X>=0,有F 0（X ）=0，当X<0时，有F 0（X ）等于负无穷。根据（2），可求出0〈X 〈W 1和X 〉=W 1情况下F 1（X ）的值。接着由（2）不断求出F 2，F 3，……，F N 在X 相应取值范围内的值。 2．2 0/1背包问题算法的抽象描述 (1)初始化各个元素的重量W[i]、效益值P[i]、包的最大容量M ； (2)初始化Ｓ0； (3)生成S i ；
最优化方法大作业答案
1.用薄钢板制造一体积5m 3，长度不小于4m ，无上盖的货箱，要求钢板耗量最小。确定货箱的长x 1、宽x 2和高x 3。试列出问题的数学模型。 解：min 32312122x x x x x x z ++= s.t 5321=x x x 41≥x 0,,321≥x x x 2.将下面的线性规划问题表示为标准型并用单纯形法求解 max f=x 1+2x 2+x 3 s ．t ．2x 1+x 2-x 3≤2 -2x 1+x 2-5x 3≥-6 4x 1+x 2+x 3≤6 x i ≥0 i=1，2，3 解：先化标准形： Min 321x x x z -+= 224321=+-+x x x x 6525321=++-x x x x 646321=+++x x x x 列成表格：
1 2 1 610011460105122001112----- 可见此表已具备1°，2°，3°三个特点，可采用单纯形法。首先从底行中选元素-1，由2/2,6/2,6/4最小者决定选第一行第一列的元素2，标以记号，迭代一次得 1 2 1 2102310401162010021212 11-------- 再从底行中选元素-2/3，和第二列正元素1/2，迭代一次得 1 2 12 32 30 210231040116201002121211- ------ 再从底行中选元素-3，和第二列正元素2，迭代一次得 4 2 3 3 410120280114042001112--- 再迭代一次得 10 2 30 2 10 6 221023 1010213000421021013-- 选取最优解：
算法设计实验_贪心算法背包问题
《算法分析与设计》 课程实验 专业年级：信息与计算科学 学生学号： 学生姓名： 实验题目：用贪婪法求解背包问题 指导老师： 实验时间：20xx年xx月x日 一、实验内容 用贪婪法求解背包问题 要求：用非递归实现 二、实验步骤 2.1、理解算法思想和问题要求； 2.2、写出每个操作的算法 非递归算法： greedbag() { int N; int c;
int[] w; int[] v; Scanner scan=new Scanner(System.in); System.out.print("输入背包的容量:"); c=scan.nextInt(); System.out.print("输入物品的数量:"); N=scan.nextInt(); System.out.print("分别输入物品的价值:"); v=new int[N]; for(int i=0;i 实验三、0-1背包问题（贪心算法） 实验代码： #include printf("物品总数为：7\n"); printf("物品重量和价值分别为：\n"); printf("\n重量价值\n"); for (i=1;i<=n;i++) printf("%d %d \n",w[i],v[i]); int m=15; int array[8][100]={0}; Knapsack(v,w,x,m,7,array); printf("背包能装的最大价值为: %d\n",array[1][m]); printf("贪心算法的解为: "); for(i=1;i<=n;i++) { if(i==1) printf("%d",x[i]); else printf(" %d",x[i]); } printf("\n"); return 0; } 测试截图为： 数学与物理科学学院 《算法分析与设计》课程考查论文 题目0-1背包问题研究及算法策略比较分析 专业 班级 学号 姓名 任课教师 完成日期2011/5/24 背包问题是一个在运筹学领域里常见的典型NP-C难题，也是算法设计分析中的经典问题，对该问题的求解方法的研究无论是在理论上,还是在实践中都具有重要意义。对这个问题的求解已经研究出了不少的经典方法，对该问题的探索和应用研究一直在进行。在先进理论指导下，求解0-1背包问题具有科学、高效、经济、灵活、方便等显著特点。 那么要解决背包问题，首要的前提就是设计出好的算法，想求得背包问题的解，就要先设计出算法,本文采用回溯法对背包问题、0-1背包问题及简单0-1背包问题进行算法设计和时间复杂度分析，给出具体算法设计和实现过程。并以具体实例详细描述不同方法求解问题解时算法基本思想，然后就解决0-1背包问题对这四种算法进行详细的比较，总结这种方法实现的优缺点并得出结论。如何将背包问题应用于实际问题中，有针对性地设计适合求解实际0-1背包问题的算法，并很好地解决实际问题，是计算机工作者不断思索、研究的一个领域。 摘要 (2) 一、绪论 (4) 1.1问题的研究及意义 (4) 1.20-1背包问题的算法研究与分析 (4) 1.3课题的主要研究内容 (4) 二、0-1背包问题在动态规划中的实现 (5) 2.1动态规划的基本原理与分析 (5) 2.20-1背包问题的实现 (5) 三、0-1背包问题在分枝-限界法中的实现 (7) 3.1分枝-限界法的基本原理与分析 (7) 3.20-1背包问题的实现 (7) 四、0-1背包问题在遗传算法中的实现 (9) 4.1遗传算法的基本原理与分析 (9) 4.20-1背包问题的实现 (10) 五、0-1背包问题在回溯法中的实现 (11) 5.1回溯法的基本原理与分析 (11) 5.20-1背包问题的实现 (11) 5.30-1背包问题在回溯法中的算法描述 (12) 5.4算法效率 (14) 5.5运行结果 (15) 六、四种算法的比较与分析 (15) 七、附录 (17) 发动机空燃比控制器 引言：我主要从事自动化相关研究。这里介绍我曾经接触过的发动机空燃比控制器设计中的优化问题。 发动机空燃比控制器设计中的最优化问题 AFR =a f m m && (1) 空燃比由方程（1）定义，在发动机运行过程中如果控制AFR 稳定在14.7可以获 得最好的动力性能和排放性能。如果假设进入气缸的空气流量a m &可以由相关单元检测得到，则可以通过控制进入气缸的燃油流量f m &来实现空燃比的精确控制。由于实际发动机的燃油喷嘴并不是直接对气缸喷燃油，而是通过进气歧管喷燃油，这么做会在进 气歧管壁上液化形成油膜，因此不仅是喷嘴喷出的未液化部分燃油会进入气缸，油膜 蒸发部分燃油也会进入气缸，如方程（2）。这样如何更好的喷射燃油成为了一个问题。 1110101122211ττττ?? ?? -?? ??????????=+????????-????????????-???? ? ??? ?? ????????? ?f f f v X x x u x x X x y =x && (2) 其中12、,==ff fv x m x m &&=f y m &,=fi u m &这里面，表示油膜蒸发量ff m &、fv m &表示为液化部分燃油、fi m &表示喷嘴喷射的燃油，在τf 、τv 、X 都已知的情况下，由现代控制理论知识，根据系统的增广状态空间模型方程（3） 0000001 1 011011114.70ττττ????-?? ??????????=-+-??????????????? ??????????????? ?? ??=?????? f f v v a X X u +q q m y q x x x &&& (3) 其中()0 14.7?t a q = y -m &。由极点配置方法，只要设计控制器方程（4），就可以 使得y 无差的跟踪阶跃输入，那么y 也能较好的跟踪AFR *a m /&。 12-- u =K q K x (4) 这里面的12、K K 确定，可由主导极点概念降维成两个参数12C ,C ，虽然都是最终稳态无差，但是目标是使得瞬态过程中y 和阶跃输入y r 的差异尽可能的小。所以原问 #include<> #define N 100 typedef struct bao{ int num; float w; float v; }; typedef struct avg{ int num; ( float val; float w; float v; }; struct bao b[N]; struct avg d[N]; int n; float c; ^ void Sort() { int i,j,k; struct avg temp[N]; for(i=0;i float x[N],sum = 0; for(i=0;i 背包问题算法设计 题目描述： 有n个物品，每个物品的重量为w[i]，取物品则效益增加p[i]，对于给定的一个能容纳重量为M的背包，怎样装包才能使获得的效益最大？每个物品的取值为x[i]，x[i]=0/1，0表示该物品不装包，1表示将该物品装入包中。 以上描述就是一个经典的0/1背包问题。 输入输出： 输入一个n，然后输入w[1,2,...,n],p[1,2,...,n] 输出最大效益值和x[1,2,...,n]用0/1表示 sampleinput 3//n 234//w[i] 125//p[i] sampleoutput 6//最大效益值 101//x[i] 解题思路： 假定决策次序为x[n],x[n-1],...,x[1]。在对x[n]做出决策之后，问题处于下列两种状态之一： 背包的剩余容量为M，没有产生任何效益； 剩余容量是M-w，效益增长了p。 显然，余下来的x[n-1],x[n-2],..,x[1]的决策相对于x所产生的问题状态应该是最优的，否则x[n],x[n-1],...,x[1]就不能是最优决策序列。 设f[j][x]是从物品1-j,背包容量为x的最优解 则最优序列的解f[n][m] 对于任意的f[i][x]=max{f[i-1][x],f[i-1][x-wi]+pi}---------------------------（1） 为了能向后递推而最后求出f[n][m],需要从f[0][x]开始。对于所有x>=0，有f[0][x]=0， 当x<0时，有f[0][x]=负无穷。根据（1）马上可解出0<=x 惯性导航基础课程大作业报告（一）光纤陀螺误差建模与分析 班级：111514 姓名： 学号 2014年5月26日 一.系统误差原理图 二.系统误差的分析 （一）漂移引起的系统误差 1. εx ，εy ，εz 对东向速度误差δVx 的影响 clc;clear all; t=1:0.01:25; g=9.8; L=pi/180*39; Ws=2*pi/84.4*60; Wie=2*pi/24; R=g/(Ws)^2; e=0.1*180/pi; mcVx1=e*g*sin(L)/(Ws^2-Wie^2)*(sin(Wie*t)-Wie*sin(Ws*t)/Ws); mcVx2=e*((Ws^2-(Wie^2)*((cos(L))^2))/(Ws^2-Wie^2)*cos(Ws*t)-(Ws^2)*((sin(L))^2)*cos(Wi e*t)/(Ws^2-Wie^2)-(cos(L))^2); mcVx3=(sin(L))*(cos(L))*R*e*((Ws^2)*cos(Wie*t)/(Ws^2-Wie^2)-(Wie^2)*cos(Ws*t)/(Ws^2-Wi e^2)-1); plot(t,[mcVx1',mcVx2',mcVx3']); title('Ex,Ey,Ez 对Vx 的影响'); xlabel('时间t'); ylabel('Vx(t)'); 0,δλδL ,v v δδ legend('Ex-mcVx1','Ey-mcVx2','Ez-mcVx3'); grid; axis square; 分析：εx，εy，εz对东向速度误差δVx均有地球自转周期的影响，εx，εy还会有舒勒周期分量的影响，其中，εy对δVx的影响较大。 2.εx，εy，εz对东向速度误差δVy的影响 clc;clear all; t=1:0.01:25; g=9.8; L=pi/180*39; Ws=2*pi/84.4*60; Wie=2*pi/24; R=g/(Ws)^2; e=0.1*180/pi; mcVy1=e*g*(cos(Wie*t)-cos(Ws*t))/(Ws^2-Wie^2); mcVy2=g*sin(L)*e/(Ws^2-Wie^2)*(sin(Wie*t)-Wie/Ws*sin(Ws*t)); mcVy3=g*cos(L)*e/(Ws^2-Wie^2)*(sin(Wie*t)-Wie/Ws*sin(Ws*t)); plot(t,[mcVy1',mcVy2',mcVy3']); title('Ex,Ey,Ez对Vy的影响'); xlabel('时间t'); ylabel('Vy(t)'); legend('Ex-mcVy1','Ey-mcVy2','Ez-mcVy3'); grid; axis square; 算法分析与设计实验报告 第 4 次实验 } 附录：完整代码 #include P01: 01背包问题 题目 有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。 基本思路 这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。 用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是： f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} 这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。 优化空间复杂度 以上方法的时间和空间复杂度均为O(VN)，其中时间复杂度应该已经不能再优化了，但空间复杂度却可以优化到O。 先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[i][0..V]的所有值。那么，如果只用一个数组f[0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。伪代码如下： for i=1..N for v=V..0 f[v]=max{f[v],f[v-c[i]]+w[i]}; 其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程 f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话，那么 实验五：贪心算法求解背包问题 实验内容 应用贪心算法求解离散背包问题，分析时间复杂度。 有一个承重为W的背包和n个物品，它们各自的重量和价值分别是wi和vi（1<=i<=n），设求这些物品中最有价值的一个子集。如果每次选择某一个物品的时候，只能全部拿走，则这一问题称为离散（0-1）背包问题；如果每次可以拿走某一物品的任意一部分，则这一问题称为连续背包问题。 算法思想 ?动态规划的思想： –对较小的子问题进行一次求解，并把结果记录下来，然后利用较小问题的解，求解出较大问题的解，直到求解出最大问题的解。 – 引进一个二维数组ch[MAX][MAX]，用ch[i][j]记录CH1与CH2的LCS 的长度，b[i][j]记录ch[i][j]是通过哪一个子问题的值求得的，以决定搜索的方向。 我们是自底向上进行递推计算，那么在计算ch[i,j]之前，ch[i-1][j-1]， ch[i-1][j]与ch[i][j-1]均已计算出来。此时我们根据CH1 [i] = CH2[j]还是CH1[i] != CH2[j]，就可以计算出ch[i][j]。 算法 length(string CH1,string CH2,int b[MAX][MAX]) //用于构建动态数组 //输入：两字符窜 //输出：最长公共子序列 for(i=1;i<=ch1Len;i++)//二重循环求解 for(int j=1;j<=ch2Len;j++) { if(CH1[i-1]==CH2[j-1])//相等字符 { ch[i][j]=ch[i-1][j-1]+1; b[i][j]=0; } else if(ch[i-1][j]>=ch[i][j-1])//上比较大 { ch[i][j]=ch[i-1][j]; b[i][j]=1; } else//左比较大 { ch[i][j]=ch[i][j-1]; b[i][j]=-1; } } printCS(int b[MAX][MAX],string x,int i,int j) //回溯求出最长子序列输出 //输入：标记数组 //输出：最长子序列 if(i == 0 || j == 0)//边界，返回 return; if(b[i][j] == 0) { printCS(b, x, i-1, j-1);//左上 cout< 算法设计与分析实验报告 题目：贪心算法背包问题 专业：JA V A技术xx——xxx班 学号： 姓名： 指导老师： 实验三：贪心算法背包问题 一、实验目的与要求 1、掌握背包问题的算法 2、初步掌握贪心算法 二、实验题： 问题描述：与0-1背包问题相似，给定n种物品和一个背包。物品i的重量是wi，其价值为vi，背包的容量为c。与0-1背包问题不同的是，在选择物品i装入背包时，背包问题的解决可以选择物品i的一部分，而不一定要全部装入背包，1< i < n。 三、实验代码 import java.awt.*; import java.awt.event.*; import javax.swing.*; public class er extends JFrame { private static final long serialVersionUID = -1508220487443708466L; private static final int width = 360;// 面板的宽度 private static final int height = 300;// 面板的高度 public int M; public int[] w; public int[] p; public int length; er() { // 初始Frame参数设置 this.setTitle("贪心算法"); setDefaultCloseOperation(EXIT_ON_CLOSE); setSize(width, height); Container c = getContentPane(); c.setLayout(new BoxLayout(c, BoxLayout.Y_AXIS)); setLocation(350, 150); // 声明一些字体样式 Font topF1 = new Font("宋体", Font.BOLD, 28); Font black15 = new Font("宋体", Font.PLAIN, 20); Font bold10 = new Font("宋体", Font.BOLD, 15); // 声明工具栏及属性设置 JPanel barPanel = new JPanel(); JMenuBar topBar = new JMenuBar(); topBar.setLocation(1, 1); barPanel.add(topBar); // 面板1和顶部标签属性设置 JPanel p1 = new JPanel(); JLabel topLabel = new JLabel("背包问题"); 算法设计与分析大作业 班级：电子154 姓名：吴志勇 学号： 1049731503279 任课老师：李瑞芳 日期： 2015.12.25 算法设计与分析课程论文 0-1背包问题的算法设计策略对比与分析 0 引言 对于计算机科学来说，算法的概念是至关重要的。在一个大型软件系统的开发中，设计出有效的算法将起到决定性的作用。通俗的讲，算法是解决问题的一种方法。也因此，《算法分析与设计》成为计算科学的核心问题之一，也是计算机科学与技术专业本科及研究生的一门重要的专业基础课。算法分析与设计是计算机软件开发人员必修课，软件的效率和稳定性取决于软件中所采用的算法；对于一般程序员和计算机专业学生，学习算法设计与分析课程，可以开阔编程思路，编写出优质程序。通过老师的解析，培养我们怎样分析算法的“好”于“坏”，怎样设计算法，并以广泛用于计算机科学中的算法为例，对种类不同难度的算法设计进行系统的介绍与比较。本课程将培养学生严格的设计与分析算法的思维方式，改变随意拼凑算法的习惯。本课程要求具备离散数学、程序设计语言、数据结构等先行课课程的知识。 1 算法复杂性分析的方法介绍 算法复杂性的高低体现在运行该算法所需要的计算机资源的多少上，所需的资源越多，该算法的复杂性越高；反之，所需资源越少，该算法的复杂性越低。对计算机资源，最重要的是时间与空间（即存储器）资源。因此，算法的复杂性有时间复杂性T(n)与空间复杂性S(n)之分。 算法复杂性是算法运行所需要的计算机资源的量，这个量应集中反映算法的效率，并从运行该算法的实际计算机中抽象出来，换句话说，这个量应该只依赖要解决的问题规模‘算法的输入和算法本身的函数。用C表示复杂性，N,I和A表示问题的规模、算法的输入和算法本身规模，则有如下表达式： C=F(N,I,A) T=F(N，I,A) S=F(N，I,A) 其中F(N,I,A)是一个三元函数。通常A隐含在复杂性函数名当中，因此表达式中一般不写A。 即：C=F(N,I) T=F(N,I) S=F(N,I) 算法复杂性中时间与空间复杂性算法相似，所以以下算法复杂性主要以时间复杂性为例： 算法的时间复杂性一般分为三种情况：最坏情况、最好情况和平均情况。下面描述算法复杂性时都是用的简化的复杂性算法分析，引入了渐近意义的记号O,Ω，θ，和o。 O表示渐近上界Ω表示渐近下界： θ表示同阶即：f(n)= O(g(n))且 f(n)= Ω（g(n)） 2 常见的算法分析设计策略介绍 2.1 递归与分治策略 分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。 直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。 由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。 分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。 递归算法举例： 共11页第1页 目标：使用带双步位移的QR 分解法求矩阵10*10[]ij A a =的全部特征值，并对其中的每一个实特征值求相应的特征向量。已知：sin(0.50.2)() 1.5cos( 1.2)(){i j i j ij i j i j a +≠+== (i,j=1,2, (10) 算法： 以上是程序运作的逻辑，其中具体的函数的算法，大部分都是数值分析课本上的逻辑，在这里特别写出矩阵A 的实特征值对应的一个特征向量的求法： ()[]()() []()[]()111111I 00000 i n n n B A I gause i n Q A I u Bu u λλ-?-?-=-?-?? ?-=????→=??????→= ?? ? 选主元的消元 检查知无重特征值 由于=0i A I λ- ，因此在经过选主元的高斯消元以后，i A I λ- 即B 的最后一行必然为零，左上方变 为n-1阶单位矩阵[]()()11I n n -?-，右上方变为n-1阶向量[]()11n Q ?-，然后令n u 1=-，则 ()1,2,,1j j u Q j n ==???-。 这样即求出所有A所有实特征值对应的一个特征向量。 #include贪心算法0-1背包问题(算法实验代码)
0-1背包问题研究及算法策略比较分析
最优化方法大作业
C语言版贪心算法背包问题
背包问题算法设计
北航惯性导航大作业
背包问题(贪心算法)
背包问题九讲(很详细)
算法设计和分析实验四：贪心算法求解背包问题
贪心算法背包问题
0-1背包问题的算法设计策略对比与讲解
北航数值分析大作业第二题精解