一、实验目的
（1）理解回溯法的思想。
（2）掌握一些经典的问题解决方法。
二、实验内容与实验步骤
0-1背包问题
★问题描述
给定n种物品和一背包。物品i的重量是wi>0，其价值为vi>0，背包的
容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总
价值最大？
★编程任务
利用回溯法试设计一个算法求出0-1背包问题的解，也就是求出一个解向量ｘi
(ｘi = 0 或１，ｘi = 0表示物体ｉ不放入背包，ｘi ＝1表示把物体ｉ放入背包），
使得尽量多的价值装入背包。
★数据输入
由文件input.txt提供输入数据n，c，及每个物品的重量w[ ]和价值v[ ]。
★结果输出
程序运行结束时，将最优解输出到文件output.txt中。
输入文件示例输出文件示例
input.txt output.txt
1 1 0 1
4
5
2 1
3 2
12 10 20 15
三、实验环境
操作系统Windows 7
调试软件VC++6.0
上机地点综合楼211
四、问题分析
（1）分析要解决的问题，给出你的思路，可以借助图表等辅助表达。
01背包问题用回溯法实现就是要枚举其所有的解空间，时间复杂度为(2)n
O左右。
搜索的具体方法如下：
对于每一个物品i，对于该物品只有选与不选2个决策，总共有n个物品，可以顺序依次考虑每个物品，这样就形成了一棵解空间
树：
基本思想就是遍历这棵树，以枚举所有情况，最后进行判断，如果重量不超过背包容量，且价值最大的话，该方案就是最后
的答案。
利用回溯算法写还可以加入一些优化，进行剪枝，因为很多情况是没有意义的，例如当重量大于背包容量的时候，没有必要对
剩下的物品再来决策了。或者将剩下的所有物品都选取其总价值也
没有目前已经求得的方案的价值还大的话，也是可以剪枝的。
（2）分析利用你的想法解决该问题可能会有怎样的时空复杂度。
时间复杂度估计：(2)n
O
因为物品只有选与不选2个决策，而总共有n个物品，所以时间复杂度为(2)n
O。
空间复杂度估计：()
O n
因为递归栈最多达到n层，而且存储所有物品的信息也只需要常数个一维数组，所以最终的空间复杂度为()
O n。
五、问题解决
（1）根据对问题的分析，写出解决办法。
根据上面的分析，搜索的具体方法如下：
对于每一个物品i，对于该物品只有选与不选2个决策，总共有n个物品，可以顺序依次考虑每个物品，这样就形成了一棵解空间
树，由父亲节点往下搜索的时候，往左表示选择该物品，并且将该
物品的重量和价值追加到总重量和总价值中，最后，当到达第n+1
层的时候，表示所有的物品都已经决策完了，可以比较和更新最优
值。
当所有的分支和节点都遍历完时，此时的最优值就是原问题的最优值。
优化方法：
剪枝一：可以进行剪枝，因为很多情况是没有意义的，当重量大于背包容量的时候，没有必要对剩下的物品再来决策了。
剪枝二：将剩下的所有物品都选取其总价值也没有目前已经求得的方案的价值还大的话，也可以返回。
（1）描述你在进行实现时，主要的函数或操作内部的主要算法；分析这个算法的时、空复杂度，并说明你设计的巧妙之处，如有创新，将其清晰的表述。
void Knapsack(Typep p[ ], Typew w[ ], Typew c, int n)
{ //为Knap::Backtrack 初始化
Typew W = 0;
Typep P = 0;
FILE *fp;
Object * Q = new Object[n];
for ( int i = 1; i <= n; i++ ) {
Q[ i-1]. ID = i;
Q[ i-1]. d =1.0*p[i]/w[i];
P += p[i];
W += w[i];
}
Sort( Q, n);//对背包里的物品按性价比排序
Knap < Typew, Typep > K;
K.p = new Typep[ n+1 ];
K.w = new Typew[ n+1 ];
K.x = new int[ n+1 ];
for (i = 1; i <= n; i++){
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;
if ((fp=fopen("output.txt","w"))==NULL)
{
fprintf(stderr, "Cannot open input file.\n");
exit(0);
}
fprintf(fp,"%d,%d,%d,%d",K.x[4],K.x[1],K.x[2],K.x[3]);
fclose(fp);
cout<<"当前最优装配:";
cout< for (i=1;i { cout<<" "<< K.x[i] ; } cout< } template void Knap { if ( i > n ) { bestp = cp; return; } if( cw + w[i] <= c){ x[i] = 1; cw += w[i]; cp += p[i]; Backtrack(i+1); cw -= w[i]; cp -= p[i]; } if( Bound(i+1)> bestp) x[i] = 0; Backtrack(i+1); } template Typep Knap { //计算上界 Typew cleft = c-cw; //剩余容量 Typep b = cp; //以物品单位重量价值递减序装入物品 while ( i<= n && w[i]<= cleft) { cleft -= w[i]; b += p[i]; i++; } //装满背包 if( i<=n ) b+= p[i]/w[i]*cleft; return b; } 算法复杂度：由于计算上界函数Bound需要O(n)时间，在最坏情况下有O(2n)个右儿子结点需要计算上界函数，故解0-1背包问题的回溯算法Backtrack所需的计算时间为O(n2n)。 算法创新：增加了对于上限的处理函数，计算右子树中解的上界时，将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包，由此得到的价值是右子树的上界，如果这个上界不能达到当前得到的最优值，则不搜索该子树。 （2）你在调试过程中发现了怎样的问题？又做了怎样的改进？ 答：在调试过程中，对于背包中物品顺序的保存始终存在问题，应该是1011，可是总是无法得出正确的结果，所以，我对数组x[i]进行了单步调试，继而发现了在前面回溯法的设计过程中存在缺陷，将x[4]误当成了x[0]，后来经过改正输出正确。 六、实验结果总结 本实验也是自己独立完成，从设计回溯法开始，到实现01背包问题的求解，从中我学到了很多，从错误的改正过程中逐渐完成了对于问题的求解。 1.程序运行截图： 2.回答以下问题： （1） 算法实现的复杂度在问题规模很大时可以接受吗？ 答：不可以接受。因为该算法是指数级别的时间复杂度为(*2)n O n ，当n 较大时，也能在一定时间内无法得出结果。空间复杂度为()O n ，还可以接受。 但是综合上面分析，时间复杂度成为极大地瓶颈。所以规模很大时不可以接受。 （2） 如果不用回溯方法还能想到其他的解决方式吗？和回溯法相比会有更好的效率吗？ 还可以用基于动态规划思想的算法。在考虑第i 个物品的决策时，前面的物品的选择方案就成为了子问题，可以建立如下状态转移方程： [1][][][]max [1][[]][]f i j f i j f i j w i v i -?=?--+? 其中f[i][j]表示前i 个物品装入容量不超过j 的背包的最优值。 时间复杂度为(*)O n C ，其中C 为背包容量。时间复杂度比回溯法要好很多。 （3） 所选用的数据结构合适吗？ 答：合适，只用到一维数组。使用的数据结构简单，易理解。能够对数组中的每个元素随机访问。 （4） 该算法都存在哪几类可能出现的情况，你的测试完全覆盖了你所想到的这些 情况吗，测试结果如何？ 答：测试全面。 输入规模为0时，程序自动结束。 输入总重量小于背包容量时，结果为所有物品的价值总和。 输入的总重量大于背包容量时，结果为能装入所有方案中最大的值。 （5）叙述通过实验你对回溯法方法的理解及其优缺点 优点：回溯法在普通的深度优先搜索的基础上增加了限界函数，对不必要的解空间树进行剪枝，使得可行解的数量大大减少，增加了搜索速度。 回溯法的设计也非常简单，即简单的枚举搜索策略，只需要分析细节过程就能增加剪枝的操作。 另外，空间复杂度通常非常小，只有搜索深度左右的空间。 缺点：回溯法虽然设计简单，但是时间复杂度非常高，通常是指数级别的。而且回溯法的难点在于限界函数的设计。 而且回溯法通常需要遍历完所有的解空间才能得出最优值，而不是像宽度优先搜索一样第一次求出的值便是最优值。 七、附录 参考资料： 《算法导论》 0-1背包动态规划解决问题 一、问题描述： 有n个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？ 二、总体思路： 根据动态规划解题步骤（问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成）找出01背包问题的最优解以及解组成，然后编写代码实现。 原理： 动态规划与分治法类似，都是把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。但不同的是，分治法在子问题和子子问题等上被重复计算了很多次，而动态规划则具有记忆性，通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。 过程： a) 把背包问题抽象化（X1，X2，…，Xn，其中 Xi 取0或1，表示第i个物品选或不选），V i表示第i个物品的价值，W i表示第i个物品的体积（重量）； b) 建立模型，即求max(V1X1+V2X2+…+VnXn)； c) 约束条件，W1X1+W2X2+…+WnXn 《算法分析与设计》实验报告 2015-2016年第2学期 实验班级： 学生姓名： 学号： 指导老师： 信息工程学院 实验项目名称：回溯算法解决0-1背包问题 实验日期：2016年5 月18 日 一、实验类型：□√验证性□设计性 二、实验目的 掌握0—1背包问题的回溯算法 三、实验内容及要求 给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 四、实验步骤 #include int cw;//当前重量 int cp;//当前价值 int bestp;//当前最优值 int *bestx;//当前最优解 int *x;//当前解 }; int Knap::Bound(int i) { //计算上界 int cleft=c-cw;//剩余容量 int b=cp; //以物品单位重量价值递减序装入物品while(i<=n&&w[i]<=cleft) { cleft-=w[i]; b+=p[i]; i++; } //装满背包 if(i<=n) b+=p[i]/w[i]*cleft; return b; } void Knap::Backtrack(int i) { if(i>n) { if(bestp 算法实验报告 ---背包问题 实验目的 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 动态规划法、回溯法解0-1背包问题 2012级计科庞佳奇 一、问题描述与分析 1.动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会 有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。 不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。 多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。1.最优化原理（最优子结构性质）最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。2.无后效性将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。3.子问题的重叠性动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。 01背包是在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2……Wn，与之相对应的价值为P1,P2……Pn。求出获得最大价值的方案。 2.回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目 标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。 在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 0-1背包问题 计科1班朱润华 2012040732 方法1：回溯法 一、回溯法描述： 用回溯法解问题时，应明确定义问题的解空间。问题的解空间至少包含问题的一个（最优）解。对于0-1背包问题，解空间由长度为n的0-1向量组成。该解空间包含对变量的所有0-1赋值。例如n=3时，解空间为：｛（0，0，0），（0，1，0），（0，0，1），（1，0，0），（0，1，1），（1，0，1），（1，1，0），（1，1，1）｝然后可将解空间组织成树或图的形式，0-1背包则可用完全二叉树表示其解空间给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 形式化描述：给定c >0, wi >0, vi >0 , 1≤i≤n.要求找一n元向量(x1,x2,…,xn,), xi∈{0,1}, ? ∑ wi xi≤c,且∑ vi xi达最大.即一个特殊的整数规划问题。 二、回溯法步骤思想描述： 0-1背包问题是子集选取问题。0-1 背包问题的解空间可以用子集树表示。在搜索解空间树时，只要其左儿子节点是一个可行节点，搜索就进入左子树。当右子树中有可能含有最优解时，才进入右子树搜索。否则，将右子树剪去。设r是当前剩余物品价值总和，cp是当前价值；bestp是当前最优价值。当cp+r<=bestp时，可剪去右子树。计算右子树上界的更好的方法是将剩余物品依次按其单位价值排序，然后依次装入物品，直至装不下时，再装入物品一部分而装满背包。 例如：对于0-1背包问题的一个实例，n=4,c=7,p=[9,10,7,4],w=[3,5,2,1]。这4个物品的单位重量价值分别为[3,2,3,5,4]。以物品单位重量价值的递减序装入物品。先装入物品4，然后装入物品3和1.装入这3个物品后，剩余的背包容量为1，只能装0.2的物品2。由此得一个解为[1,0.2,1,1]，其相应价值为22。尽管这不是一个可行解，但可以证明其价值是最优值的上界。因此，对于这个实例，最优值不超过22。 在实现时，由Bound计算当前节点处的上界。类Knap的数据成员记录解空间树中的节点信息，以减少参数传递调用所需要的栈空间。在解空间树的当前扩展节点处，仅要进入右子树时才计算上界Bound,以判断是否可将右子树剪去。进入左子树时不需要计算上界，因为上界预期父节点的上界相同。 三、回溯法实现代码： #include "stdafx.h" #include 算法分析与设计实验报告第五次附加实验 附录： 完整代码（回溯法） //0-1背包问题回溯法求解 #include Typew c; //背包容量 int n; //物品数 Typew *w; //物品重量数组| Typep *p; //物品价值数组 Typew cw; //当前重量 Typep cp; //当前价值 Typep bestp; //当前最后价值 }; template 深圳大学实验报告课程名称：算法分析与复杂性理论 实验名称：实验四动态规划 学院：计算机与软件学院专业：软件工程 报告人：文成学号：2150230509班级：学术型 同组人：无 指导教师：杨烜 实验时间：2015/11/5——2015/11/18 实验报告提交时间：2015/11/18 教务处制 一． 实验目的与实验内容 实验目的： （1） 掌握动态规划算法设计思想。 （2） 掌握背包问题的动态规划解法。 实验内容： 1.编写背包问题的动态规划求解代码。 2．背包容量为W ，物品个数为n ，随机产生n 个物品的体积（物品的体积不可大于W ）与价值，求解该实例的最优解。 3. 分别针对以下情况求解 第一组：（n=10,W=10），（n=10,W=20），（n=10,W=30） 第二组：（n=20,W=10），（n=20,W=20），（n=20,W=30） 第三组：（n=30,W=10），（n=30,W=20），（n=30,W=30） 4. 画出三组实验的时间效率的折线图，其中x 轴是W 的值，y 轴是所花费的时间，用不同的颜色表示不同n 所花费的时间。 二．实验步骤与结果 背包问题的问题描述： 给定n 种物品和一个背包。物品i 的重量是 i w ， 其价值为i v ， 背包容量为C 。问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大？ 背包问题的算法思想： 考虑一个由前i 个物品（1<=i<=n ）定义的实例，物品的重量分别为w1，…，w2、价值分别为v1，…，vi ，背包的承重量为j （1<=j<=w ）。设v[i,j]为该实例的最优解的物品总价值，也就是说，是能够放进承重量为j 的背包中的前i 个物品中最有价值子集的总价值。可以把前i 个物品中能够放进承重量为j 的背包中的子集分成两个类别：包括第i 个物品的子集和不包括第i 个物品的子集。 1. 根据定义，在不包括第i 个物品的子集中，最优子集的价值是V[i-1,j]。 2. 在包括第i 个物品的子集中（因此，j-wi>=0），最优子集是由该物品和前i-1个物品中能够放进承重量为j-wi 的背包的最优子集组成。这种最优子集的总价值等于vi+V[i-1,j-wi]。 因此，在前i 个物品中最优解得总价值等于这两个价值中的最大值。当然，如果第i 个物品不能放进背包，从前i 个物品中选出的最优子集的总价值等于从前i-1个物品中选出的最优子集的总价值。这个结果导致了下面的这个递推关系式： 初始条件： #include 课程设计报告 课程名称数据结构课程设计 课题名称背包问题 专业信息与计算科学 班级1001班 学号22 姓名王锐 指导教师刘洞波张晓清郭芳 2012年6月9日 课程设计任务书 课程名称数据结构课程设计课题背包问题 专业班级信科1001班 学生姓名王锐 学号22 指导老师刘洞波张晓清郭芳 审批刘洞波张晓清郭芳 任务书下达日期：2012年6月9日 任务完成日期：2012年6月16日 一、设计内容与设计要求 1．设计内容： 1）问题描述 假设有一个能装入总体积为T的背包和n件体积分别为W1，W2，···，Wn的物品，能否从n件物品中挑选若干件恰好装满背包，即使W1+W2+···+Wn=T，要求找出所有满足 上述条件的解。例如：当T=10，共6件物品，物品的体积为{1，2，3，4，5，8}，那么 可找到下列4组解：（1，2，3，4）、（1，4，5）、（2，3，5）、（2、8）。 2）实现提示 可利用回溯法的设计思想来解决背包问题。首先，将物品排成一列，然后顺序选取物品装入背包，假设已选取了前i件物品之后背包还没有装满，则继续选取第i+1件物品， 若该件物品“太大”不能装入，则丢弃而继续选取下一件，直至背包装满为止。但如果在 剩余的物品中找不到合适的物品以填满背包，则说明“刚刚”装入背包的那件物品“不合 适”，应将它取出“丢弃一边”，继续再从“它之后”的物品中选取，如此重复，直至求得 满足条件的解，或者无解。 由于回溯求解的规则是“后进先出”，因此要用到栈。 2．设计要求： 课程设计报告规范 1)需求分析 a.程序的功能。 b.输入输出的要求。 2)概要设计 a.程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块的功能。 b.课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样的结构， 它们之间有什么关系等。 3)详细设计 a.采用C语言定义相关的数据类型。 b.写出各模块的类C码算法。 c.画出各函数的调用关系图、主要函数的流程图。 实验5 分支界限法解0-1背包问题 一、实验要求 1．要求用分支界限法求解0-1背包问题； 2．要求交互输入背包容量，物品重量数组，物品价值数组； 3．要求显示结果。 二、实验仪器和软件平台 仪器：带usb接口微机 软件平台：WIN-XP + VC++6.0 三、源程序 #include "stdafx.h" #include ~Knap(); float Bound(int i,int cw,int cp);//计算上界限 node *nnoder(node *pa,int ba,float uub);//生成一个结点ba=1生成左节点ba=0生成右节点 void addnode(node *nod);//向队列中添加活结点 void deletenode(node *nod);//将结点从队列中删除 struct node *nextnode(); //取下一个节点 void display(); //输出结果 void solvebag(); //背包问题求解 }; //按物品单位重量的价值排序 void Knap::Sort() { int i,j,k,kkl; float minl; for(i=1;i 1、实验目的 （1）掌握回溯法设计策略。 （2）通过0-1背包问学习回溯法法设计技巧2.实验内容 源程序： #include } if(cw+w[i]<=c) //搜索左子树 { cw+=w[i]; cp+=p[i]; Backtrack(i+1); cp-=p[i]; cw-=w[i]; } if(bound(i+1)>bestp)//搜索右子树 Backtrack(i+1); } double Knapsack (double pp[],double ww[],double d) { int i; double TP=0,TW=0; cw=0.0;cp=0.0;bestp=0.0;//计算所有物品的重量及价值 for(i=1;i<=n;i++) { TP=TP+pp[i]; TW=TW+ww[i]; } if(TW<=d)//所有物品装入背包 bestp=TP; else { Backtrack(1); } return bestp; }; int main() { 《算法设计与分析》上机实验报告 一、分治与递归 1、问题描述 编写程序，实现线性时间内选择n个元素的中位数的算法。并对于不同的n，测试平均时间效率。 2、问题分析 本问题属于线性选择问题的一个特例，可以使用分治法进行求解。其基本思想是模仿快速排序方法，对输入的数组进行划分，求出中位数所在的子数组，然后用递归的方法进行求解，最终可以求得问题的解。 3、算法设计 将n个输入元素根据随机选择的基准划分成2个子数组，a[p:r]被划分成a[p:i]和a[i+1:r]两组，使得a[p:i]中每个元素都不大于a[i+1:r]中元素。接着算法计算子数组a[p:i]中元素个数j，如果k<=j，则a[p:r]中第k个小元素落在子数组a[p:i]中元素均小于要找的第k小元素，因此要找的a[p:r]中第k小元素是a[i+1:r]中的第k-j小元素。 按照上述的方法递归的执行，直到当前数组中只剩下一个元素，就可以得到问题的解。 4、算法实现 #include"iostream.h" #include"stdlib.h" #include"time.h" #include void main() { srand((unsigned int)time(NULL)); _timeb time0,time1; int n; cout << "请输入数组的长度："; cin >> n; cout << "请输入数组的每一个数：" << endl; int *a=new int[n]; for(int i=0;i 人工智能之遗传算法求解0/1背包问题实验报告 Pb03000982 王皓棉 一、问题描述： 背包问题是著名的ＮＰ完备类困难问题, 在网络资源分配中有着广泛的应用，已经有很多人运用了各种不同的传统优化算法来解决这一问题，这些方法在求解较大规模的背包问题时,都存在着计算量大,迭代时间长的弱点。而将遗传算法应用到背包问题的求解，则克服了传统优化方法的缺点,遗传算法是借助了大自然的演化过程,是多线索而非单线索的全局优化方法,采用的是种群和随机搜索机制。 遗传算法（GA）是一类借鉴生物界自然选择和自然遗传机制的随机化的搜索算法，由美国J.Holland教授提出，其主要特点是群体搜索策略、群体中个体之间的信息交换和搜索不依赖于梯度信息。因此它尤其适用于处理传统搜索方法难于解决的复杂和非线性问题，可广泛应用于组合优化，机器学习，自适应控制，规划设计和人工生命领域。 GA是一种群体型操作，该操作以群体中的所有个体为对象。选择，交叉和变异是遗传算法的三个主要算子，他们构成了遗传算法的主要操作，使遗传算法具有了其它传统方法所没有的特性。遗传算法中包含了如下五个基本要素：1 .参数编码,2.初始群体的设置,3.适应度函数的设计, 4.遗传操作设计,5.控制参数设定,这个五个要素构成可遗传算法的核心内容。 遗传算法的搜索能力是由选择算子和交叉算子决定,变异算子则保证了算法能够搜索到问题空间的每一个点,从而使其具有搜索全局最优的能力.而遗传算法的高效性和强壮性可由Holland提出的模式定理和隐式并行性得以解释。 二、实验目的： 通过本实验，可以深入理解遗传算法，以及遗传算法对解决NP问题的作用。 三、算法设计： 1、确定种群规模M、惩罚系数 、杂交概率c p、变异概率m P、染色体长度n及最大 max. 进化代数gen x=1表 2、采用二进制n维解矢量X作为解空间参数的遗传编码，串T的长度等于n， i x=0表示不装入背包。例如X={0，1，0，1，0，0，1}表示第2，4，7示该物件装入背包， i 这三个物件被选入包中。 实验4 回溯法解0-1背包问题 一、实验要求 1．要求用回溯法求解0-1背包问题； 要求交互输入背包容量，物品重量数组，物品价值数组；2．要求显示结果。3． 二、实验仪器和软件平台 仪器：带usb接口微机 软件平台：WIN-XP + VC++ 三、实验源码 #include \ #include { bag[i].flag=0; bag[i].kk=i; bag[i].fl=*bag[i].v/bag[i].w; } }void Backtrack(int i){cw+=bag[i].w;if(i>=n) <=c) lag=1; cp+=bag[i].v; Backtrack(i+1); cw-=bag[i].w; cp-=bag[i].v; } if(Bound(i+1)>bestp)lag=0; Backtrack(i+1); }}<=cleft){; b+=bag[i].v; i++; } /bag[i].w * cleft; return b; } void Knapsack() k]=bag[k].flag; lag*bag[k].v; //价值累加 } cout< 课程设计说明书 设计题目： 0-1背包问题的动态规划算法设计 专业：班级： 设计人： 山东科技大学 2013年12月5日 课程设计任务书 学院：专业：班级：姓名： 一、课程设计题目： 二、课程设计主要参考资料 （1）计算机算法设计与分析（第3版）王晓东著 （2） 三、课程设计应解决的主要问题 （1） 0-1背包问题的动态规划算法设计 （2） （3） 四、课程设计相关附件（如：图纸、软件等）： （1） （2） 五、任务发出日期： 2013-11-21 课程设计完成日期： 2013-12-5 指导教师签字：系主任签字： 指导教师对课程设计的评语 成绩： 指导教师签字： 年月日 0-1背包问题的实现 一、设计目的 1.运用动态规划思想，设计解决上述问题的算法，找出最大背包价值的装法。 2.掌握动态规划的应用。 二、设计要求 给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品装入背包多次，也不能只装入部分的物品。0-1背包问题是一个特殊的整数规划问题。 三、设计说明 （一）、需求分析 1、问题描述： 形式化描述：给定c >0, w i>0, v i>0 , 1≤i≤n.要求找一n元向量(x1,x2,…,xn,), xi∈{0,1}, ?∑w i x i≤c,且∑v i x i达最大.即一个特殊的整数规划问题。 2、最优子结构性质： 设(y1,y2,…,y n)是(3.4.1)的一个最优解.则(y2,y3,…,y n)是下面相应子问题的一个最优解: 证明:使用反证法。若不然,设(z2,z3,…,z n)是上述子问题的一个最优解,而(y2,y3,…,y n)不是它的最优解。显然有 ∑v i z i> ∑v i y i(i=2,…,n) 且w1y1+ ∑w i z i<= c 实验5 分支界限法解0-1背包问题一、实验要求 1．要求用分支界限法求解0-1背包问题； 2．要求交互输入背包容量，物品重量数组，物品价值数组； 3．要求显示结果。 二、实验仪器和软件平台 仪器：带usb接口微机 软件平台：WIN-XP + VC++ 三、源程序 #include "" #include float ub; //结点的上界值 }; //类Knap中的数据记录解空间树中的结点信息，以减少参数传递及递归调用所需的栈空间class Knap { private: struct node *front, //队列队首 *bestp,*first; //解结点、根结点 int *p,*w,n,c,*M;//背包价值、重量、物品数、背包容量、记录大小顺序关系 long lbestp;//背包容量最优解 public: void Sort(); Knap(int *pp,int *ww,int cc,int nn); ~Knap(); float Bound(int i,int cw,int cp);//计算上界限 node *nnoder(node *pa,int ba,float uub);//生成一个结点 ba=1生成左节点 ba=0生成右节点 void addnode(node *nod);//向队列中添加活结点 void deletenode(node *nod);//将结点从队列中删除 struct node *nextnode(); //取下一个节点 void display(); //输出结果 void solvebag(); //背包问题求解 }; //按物品单位重量的价值排序 void Knap::Sort() { 回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中按照深度优先的策略，从根节点出发搜索解空间树。算法搜索至解空间树的任一节点时，总是先判断该节点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该节点为根的子树的系统搜索，逐层向其原先节点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。 运用回溯法解题通常包含以下三个步骤： ?针对所给问题，定义问题的解空间； ?确定易于搜索的解空间结构； ?以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索； 在0／1背包问题中，容量为M的背包装载。从n个物品中选取装入背包的物品，物品i的重量为Wi，价值为Pi。最佳装载指装入的物品价值最高，即∑PiXi(i=1..n)取最大值。约束条件为∑WiXi ≤M且Xi∈[0,1](1≤i≤n)。 在这个表达式中，需求出Xi的值。Xi=1表示物品i装入背包，Xi＝0表示物品i不装入背包。 ?即判断可行解的约束条件是：∑WiXi≤M（i=0..n），Wi>0,Xi∈[0,1](1≤i≤n) ?目标最大值：max∑PiXi（i=0..n-1）,Pi>0,Xi=0或1（0≤i 算法设计与分析实验报告实验二 0-1背包 院系： 班级： 学号： 姓名： 任课教师： 成绩： 年月 实验二 0-1背包 一. 实验内容 分别用编程实现动态规划算法和贪心法求0-1背包问题的最优解，分析比较两种算法的时间复杂度并验证分析结果 二．实验目的 1、掌握动态规划算法和贪心法解决问题的一般步骤，学会使用动态规划和贪心法解决实际问题； 2、理解动态规划算法和贪心法的异同及各自的适用范围。 三. 算法描述 1、动态规划法 01背包问题的状态转换公式为： （1） V(i, 0)= V(0, j)=0 （2） 公式表明：把前面i 个物品装入容量为0的背包和把0个物品装入容量为j 的背包，得到的价值均为0。如果第i 个物品的重量大于背包的容量，则装入前i 个物品得到的最大价值和装入前i -1个物品得到的最大价值是相同的，即物品i 不能装入背包；如果第i 个物品的重量小于背包的容量，则会有以下两种情况： （1）如果把第i 个物品装入背包，则背包中物品的价值等于把前i -1个物品装入容量为j -wi 的背包中的价值加上第i 个物品的价值vi ； （2）如果第i 个物品没有装入背包，则背包中物品的价值就等于把前i -1个物品装入容量为j 的背包中所取得的价值。显然，取二者中价值较大者作为把前i 个物品装入容量为j 的背包中的最优解。 2、贪心法 背包问题至少有三种看似合理的贪心策略： （1）选择重量最轻的物品，因为这可以装入尽可能多的物品，从而增加背包的总价值。但是，虽然每一步选择使背包的容量消耗得慢了，但背包的价值却没能保证迅速增长，从而不能保证目标函数达到最大。 （2）选择价值最大的物品，因为这可以尽可能快地增加背包的总价值。但是，虽然每一步选择获得了背包价值的极大增长，但背包容量却可能消耗得太快，使得装入背包的物品个数减少，从而不能保证目标函数达到最大。 （3）选择单位重量价值最大的物品，在背包价值增长和背包容量消耗两者 ?? ?>+---<-=i i i i w j v w j i V j i V w j j i V j i V }),1(),,1(max{) ,1(),( 用回溯法解决3种可选择物品的0-1背包问题当n=3时，其解空间是 {（0,0,0）（0,1,0），（0,0,1），（1,0,0），（0,1,1），（1,0,1），（1,1,0），（1,1,1）}n=3时的0-1背包问题： w=[16,15,15]p=[45,25,25]c=30 开始时，Cr=C=30，V=0，A为唯一活结点，也是当前扩展结点 扩展A，先到达B结点 Cr=Cr-w1=14，V=V+v1=45 此时A、B为活结点，B成为当前扩展结点 扩展B，先到达D Cr Cr=30，V=0，活结点为A、C，C为当前扩展结点 扩展C，先到达F Cr=Cr-w2=15，V=V+v2=25，此时活结点为A、C、F，F成为当前扩展结点扩展F，先到达L Cr=Cr-w3=0，V=V+v3=50 L是叶结点，且50>45，皆得到一个可行解x=(0,1,1)，V=50 L不可扩展，成为死结点，返回到F 再扩展F到达M M是叶结点，且25<50，不是最优解 M不可扩展，成为死结点，返回到F F没有可扩展结点，成为死结点，返回到C 再扩展C到达G Cr=30，V=0，活结点为A、C、G，G为当前扩展结点 扩展G，先到达N，N是叶结点，且25<50，不是最优解，又N不可扩展，返回到G 再扩展G到达O，O是叶结点，且0<50，不是最优解，又O不可扩展，返回到G G没有可扩展结点，成为死结点，返回到C C没有可扩展结点，成为死结点，返回到A A没有可扩展结点，成为死结点，算法结束，最优解X=(0,1,1)，最优值 V=50动态规划与回溯法解决0-1背包问题
回溯算法解决0-1背包问题(DOC)
算法设计背包问题
算法分析与程序设计动态规划及回溯法解背包问题
回溯法和分支限界法解决0-1背包题
回溯法实验(0-1背包问题)
算法分析与复杂性理论 实验报告 背包问题
用回溯法解决0-1背包问题
背包问题
分支界限法解0-1背包问题实验报告
回溯算法之0-1背包问题
算法实验报告
人工智能之遗传算法求解01背包问题实验报告
回溯法解0 1背包问题实验报告
0-1背包问题
分支界限法解0-1背包问题实验报告
回溯法解决01背包问题
01背包实验报告
(原创精品)n=3时的0-1背包问题(回溯法)
相关主题
文本预览