算法分析与复杂性理论 实验报告 凸包问题

实验报告. 基于回溯法的0-1背包等问题实验内容本实验要求基于算法设计与分析的一般过程（即待求解问题的描述、算法设计、算法描述、算法正确性证明、算法分析、算法实现与测试），通过回溯法的在实际问题求解实践中，加深理解其基本原理和思想以及求解步骤。

求解的问题为0-1背包。

作为挑战：可以考虑回溯法在如最大团、旅行商、图的m着色等问题中的应用。

实验目的◆理解回溯法的核心思想以及求解过程（确定解的形式及解空间组织，分析出搜索过程中的剪枝函数即约束函数与限界函数）；◆掌握对几种解空间树（子集树、排列数、满m叉树）的回溯方法；◆从算法分析与设计的角度，对0-1背包等问题的基于回溯法求解有进一步的理解。

环境要求对于环境没有特别要求。

对于算法实现，可以自由选择C, C++或Java，甚至于其他程序设计语言如Python等。

实验步骤步骤1：理解问题，给出问题的描述。

步骤2：算法设计，包括策略与数据结构的选择。

步骤3：描述算法。

希望采用源代码以外的形式，如伪代码或流程图等；步骤4：算法的正确性证明。

需要这个环节，在理解的基础上对算法的正确性给予证明；步骤5：算法复杂性分析，包括时间复杂性和空间复杂性；步骤6：算法实现与测试。

附上代码或以附件的形式提交，同时贴上算法运行结果截图；步骤7：技术上、分析过程中等各种心得体会与备忘，需要言之有物。

说明：步骤1-6在“实验结果”一节中描述，步骤7在“实验总结”一节中描述。

实验结果步骤1：问题描述。

给定 n个物品，其中第 i 个物品的重量为w i ，价值为 v i 。

有一容积为 W 的背包，要求选择一些物品放入背包，使得物品总体积不超过W的前提下，物品的价值总和最大。

0-1背包问题的限制是，每种物品只有一个，它的状态只有放和不放两种。

0-1背包问题是特殊的整数规划问题，其可用数学语言表述为：对于给定 n >0,W >0,v,w (v i ,w i >0,1≤i ≤n)，找出一个 n 元0-1向量x =( x 1, x 2,⋯, x n ) 其中x i ∈{0,1},1≤i ≤n ，使得∑v i n i=1x i 最大，并且∑w i n i=1x i ≤W ，即：max x (∑v i ni=1x i ) s.t.∑w i ni=1x i ≤W, x i ∈{0,1},1≤i ≤n步骤2：算法设计，即算法策略与数据结构的选择。

算法分析与设计实验报告[0/1背包问题]0/1背包问题的不同算法解决方案组员02黄希龙 09455321张育强05周麒目录一.问题描述 (1)二.算法分析 (2)1.穷举法： (2)2.递归法： (4)3.贪心法： (5)4.动态规划法分析： (6)5.回溯法分析： (7)6.分支限界法： (9)三.时空效率分析 (10)1.穷举法： (10)2.递归法： (11)3.动态规划法： (11)4.回溯法： (11)5分支限界法： (11)四.运行结果 (12)1.穷举法输出结果： (12)2.递归法输出结果： (13)3.动态规划法输出结果： (14)4.回溯法输出结果： (15)5.分支限界法输出结果： (16)五.分析输出结果 (17)六.总结与反思 (18)一.问题描述0/1背包问题:现有n 种物品，对1<=i<=n ，已知第i 种物品的重量为正整数W i ，价值为正整数V i ，背包能承受的最大载重量为正整数W ，现要求找出这n 种物品的一个子集，使得子集中物品的总重量不超过W 且总价值尽量大。

（注意：这里对每种物品或者全取或者一点都不取，不允许只取一部分）二.算法分析根据问题描述，可以将其转化为如下的约束条件和目标函数：)2(max )1()1}(1,0{11∑∑==⎪⎩⎪⎨⎧≤≤∈≤ni i i ini i i x v n i x Wx w 于是，问题就归结为寻找一个满足约束条件（1），并使目标函数式（2）达到最大的解向量),......,,,(321n x x x x X =。

首先说明一下0-1背包问题拥有最优解。

假设),......,,,(321n x x x x 是所给的问题的一个最优解，则),......,,(32n x x x 是下面问题的一个最优解：∑∑==⎪⎩⎪⎨⎧≤≤∈-≤ni i i ini i i x v n i x x w W x w 2211max )2}(1,0{。

深圳大学实验报告课程名称：算法分析与复杂性理论实验名称：实验四动态规划学院：计算机与软件学院专业：软件工程报告人：文成学号：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]。

深圳大学实验报告课程名称：算法设计与分析实验名称：多种排序算法的算法实现及性能比较学院：计算机与软件学院专业：计算机科学与技术报告人：张健哲学号： 2013150372 班级： 3 同组人：无指导教师：李炎然实验时间： 2015/3/25——2015/4/8 实验报告提交时间： 2015/4/8教务处制一．实验目的1.掌握选择排序、冒泡排序、合并排序、快速排序、插入排序算法原理2.掌握不同排序算法时间效率的经验分析方法，验证理论分析与经验分析的一致性。

二．实验步骤与结果实验总体思路：利用switch结构来选择实验所要用的排序算法，每一种排序都用相同的计算运行时间的代码，不同的算法就在算法实现部分进行改动（如下代码1至5所示）。

不断的改变数据规模，每一个规模在实验时，用循环进行多次实验并作为样本记录消耗的时间。

最后输出在不同排序算法下，不同的数据规模的20次实验样本和平均用时（如下图1至5所示）。

各排序算法的实现及实验结果：（注1：以下代码全部为伪代码，具体代码实现请参照程序中的代码）（注2：图中显示的时间单位均为毫秒，图中“排序所花时间”一项为平均消耗时间，平均消耗时间结果以20组样本计算平均值后取整得到（并非四舍五入）。

）1、选择排序代码1：for i=0 to n-2min=ifor j= i+1 to n-1if ele[min]>ele[j] min=jswap(ele[i],ele[min]) //交换图1、选择排序在不同数据规模下排序所消耗的时间2、冒泡排序代码2：for i= 0 to n-1for j=0 to n-1-iif a[j]>a[j+1]swap(a[j],a[j+1]) //交换图2、冒泡排序在不同数据规模下排序所消耗的时间3、合并排序代码3：Merge(ele[1...n],left,right)middle=(left+right)/2if right>1eft+1Merge(ele,left,middle)Merge(ele,middle+1,right)l←left r←right i←leftwhile l<=middle&&r<=right //两组分别一一比较，数据小的放入ele if ele[l]<=ele[r]t[i++]←ele[l++]elset[i++]←ele[r++]while l>middle&&r<=r //只剩一组还有剩余的时，将剩下的按顺序放入ele[i++]=s[r++]while l<=middle && r>rightele[i++]=s[l++];图3、合并排序在不同数据规模下排序所消耗的时间4、快速排序代码4：quick(ele[0...n-1],left,right)if l<rl←left r←right x←ele[l];while l<rwhile l<r && x<=ele[r] //找到一个比x小的数之后交换到前面的部分r--if l<rele[l]←ele[r] l++while l<r && x>ele[l] //与上面相反ll++if l<rele[r]←ele[l] r--ele[l]←x;quick(ele,left,l-1) // 递归调用quick(ele,l+1,right)图4、快速排序在不同数据规模下排序所消耗的时间5、插入排序代码5：for i=1→n-1if ele[i]<ele[i-1] temp=ele[i]for j= i-1 to 0 && ele[j]>tempele[j+1]←ele[j]ele[j+1]←temp图5、插入排序在不同数据规模下排序所消耗的时间三．实验分析选择排序：图6、由图1数据整合而成的折线图为了更清晰的看到排序的数据规模与排序所需时间之间的影响，我将实验的数据规模进行了一些调整，得到的平均数据依旧是以20组数据样本取平均数算得（如下表1、图7所示）：（由于图片占空间大且表达不直白，我将所得数据做成表格分析，下同）表1、选择排序在不同数据规模下排序所消耗的时间图7、由表1数据整合而成的折线图图形上：形状基本符合n2（二次增长）数据上：我们发现当数据规模增大两倍时：当数据规模增大两倍时：10000→20000： 158*22=632≈634 10000→30000：158*32=1422≈142420000→40000： 634*22=2536≈2541其他倍数也可得到类似的结果。

【算法】凸包问题--分治法凸包问题--分治法求能够完全包含平⾯上n个给定点的凸多边形。

⽰例：⼀、分治法：（⼀）算法思路：（这⾥所说的直线都是有向直线的。

）将数组升序排序，若x轴坐标相同，按照y轴坐标升序排序。

最左边的点p1和最右边的点p_n⼀定是该集合凸包的顶点。

该直线将点分为两个集合，上包为S1，下包为S2。

在p1 p_n线上的点不可能是凸包的顶点，所以不⽤考虑。

在上包S1中，找到p_max(距离直线p1p_n最远距离的点)，若有两个距离同样远的点，取∠p_max p1 p_n最⼤的那个点（即△p_max p1 p_n⾯积最⼤）。

（⼀次递归到这⾥结束）找出S1中所有在直线p1 p_max左边的点，这些点中⼀定有构成上包中左半部分边界的顶点，⽤上⾯的算法递归查找点，直到上包就是以p1和p_n 为端点的线段。

下包S2中找下边界同理。

*如何判断点是否在直线p1 p_max左边（同 p1 p_n上⽅）？如果q1（x1，y1），q2（x2，y2），q3（x3，y3）是平⾯上的任意三个点，那么三⾓形△q1 q2 q3的⾯积等于下⾯这个⾏列式绝对值的⼆分之⼀。

当且仅当点q3=（x3，y3）位于直线q1 q2的左侧时，该表达式的符号为正，该点位于两个点确定的直线的左侧。

（⼆）实现中碰到的问题如何⽤快速排序来排序Point类（内有坐标x,y）的⼀维数组？按照x坐标排序很简单，若碰到x相同，y不同的怎么办？在快排的原基础上修改，以j向前逼近说明：（第⼀个while循环）当前⽐较数的横坐标>基准点的时，j向前逼近。

此处不加等于号，排序是不稳定的，即相等元素的相对位置可能发⽣改变。

（快排详见博客：（第⼆个while为添加内容）⽐较相等元素的纵坐标，基准点的更⼩，j继续向前逼近，即相等元素的相对位置不发⽣改变；否则，则改变。

也就是将原来快排中while循环拆分为两个，增加相等元素另外⽐较纵坐标的情况。

while (i < j && points[j].getX() > center.getX()) {j--;}while (i < j && center.getX() == points[j].getX() && points[j].getY() > center.getY()) {j--;}/** (i<j)若points[j].getX()< center.getX()或 center.getX() ==* points[j].getX()且points[j].getY()<center.getY() 以上两种情况，需要赋值*/if (i < j)// 跳出循环也有可能时因为i=j，所以这⾥要判断⼀下points[i++] = points[j];如果使⽤全局数组visit标识点是否访问，能确定凸包的所有顶点，但怎么顺序输出?在已经求的凸包顶点⾥逐⼀确定边界，判断是不是所有点都在这条边界的⼀侧，如果是则确定⼀条边界。

关于凸包问题Graham扫描法基本思想：通过设置⼀个关于候选点的堆栈s来解决凸包问题。

操作：输⼊集合Q中的每⼀个点都被压⼊栈⼀次，⾮CH（Q）(表⽰Q的凸包)中的顶点的点最终将被弹出堆栈，当算法终⽌时，堆栈S中仅包含CH(Q)中的顶点，其顺序为个各顶点在边界上出现的逆时针⽅向排列的顺序。

注：下列过程要求|Q|>=3，它调⽤函数TOP（S）返回处于堆栈S 顶部的点，并调⽤函数NEXT-TO –TOP（S）返回处于堆栈顶部下⾯的那个点。

但不改变堆栈的结构。

GRAHAM-SCAN(Q)1 设P0 是Q 中Y 坐标最⼩的点，如果有多个这样的点则取最左边的点作为P0；2 设<P1,P2,……,Pm>是Q 中剩余的点，对其按逆时针⽅向相对P0 的极⾓进⾏排序，如果有数个点有相同的极⾓，则去掉其余的点，只留下⼀个与P0 距离最远的那个点；3 PUSH(p0 , S)4 PUSH(p1 , S)5 PUSH(p3 , S)6 for i ← 3 to m7 do while 由点NEXT-TOP-TOP（S），TOP（S）和Pi 所形成的⾓形成⼀次⾮左转8 do POP(S)9 PUSH(pi , S)10 return S⾸先，找⼀个凸包上的点，把这个点放到第⼀个点的位置P0。

然后把P1~Pm 按照P0Pi的⽅向排序，可以⽤⽮量积(叉积)判定。

做好了预处理后开始对堆栈中的点<p3,p4,...,pm>中的每⼀个点进⾏迭代，在第7到8⾏的while循环把发现不是凸包中的顶点的点从堆栈中移去。

（原理：沿逆时针⽅向通过凸包时，在每个顶点处应该向左转。

因此，while循环每次发现在⼀个顶点处没有向左转时，就把该顶点从堆栈中弹出。

）当算法向点pi推进、在已经弹出所有⾮左转的顶点后，就把pi压⼊堆栈中。

举例如下： ⽮量的概念： 如果⼀条线段的端点是有次序之分的，我们把这种线段成为有向线段(directed segment)。

第1篇一、实验目的本次实验旨在通过实际操作，加深对算法设计方法、基本思想、基本步骤和基本方法的理解与掌握。

通过具体问题的解决，提高利用课堂所学知识解决实际问题的能力，并培养综合应用所学知识解决复杂问题的能力。

二、实验内容1. 实验一：排序算法分析- 实验内容：分析比较冒泡排序、选择排序、插入排序、快速排序、归并排序等基本排序算法的效率。

- 实验步骤：1. 编写各排序算法的C++实现。

2. 使用随机生成的不同规模的数据集进行测试。

3. 记录并比较各算法的运行时间。

4. 分析不同排序算法的时间复杂度和空间复杂度。

2. 实验二：背包问题- 实验内容：使用贪心算法、回溯法、分支限界法解决0-1背包问题。

- 实验步骤：1. 编写贪心算法、回溯法和分支限界法的C++实现。

2. 使用标准测试数据集进行测试。

3. 对比分析三种算法的执行时间和求解质量。

3. 实验三：矩阵链乘问题- 实验内容：使用动态规划算法解决矩阵链乘问题。

- 实验步骤：1. 编写动态规划算法的C++实现。

2. 使用不同规模的矩阵链乘实例进行测试。

3. 分析算法的时间复杂度和空间复杂度。

4. 实验四：旅行商问题- 实验内容：使用遗传算法解决旅行商问题。

- 实验步骤：1. 设计遗传算法的参数，如种群大小、交叉率、变异率等。

2. 编写遗传算法的C++实现。

3. 使用标准测试数据集进行测试。

4. 分析算法的收敛速度和求解质量。

三、实验结果与分析1. 排序算法分析- 通过实验，我们验证了快速排序在平均情况下具有最佳的性能，其时间复杂度为O(nlogn)，优于其他排序算法。

- 冒泡排序、选择排序和插入排序在数据规模较大时效率较低，不适合实际应用。

2. 背包问题- 贪心算法虽然简单，但在某些情况下无法得到最优解。

- 回溯法能够找到最优解，但计算量较大，时间复杂度较高。

- 分支限界法结合了贪心算法和回溯法的特点，能够在保证解质量的同时，降低计算量。

3. 矩阵链乘问题- 动态规划算法能够有效解决矩阵链乘问题，时间复杂度为O(n^3)，空间复杂度为O(n^2)。

凸包算法详解Graham扫描法时间复杂度：O(n㏒n)思路：Graham扫描的思想是先找到凸包上的⼀个点，然后从那个点开始按逆时针⽅向逐个找凸包上的点，实际上就是进⾏极⾓排序，然后对其查询使⽤。

步骤：1. 把所有点放在⼆维坐标系中，则纵坐标最⼩的点⼀定是凸包上的点，如图中的P0。

2. 把所有点的坐标平移⼀下，使 P0 作为原点，如上图。

3. 计算各个点相对于 P0 的幅⾓α，按从⼩到⼤的顺序对各个点排序。

当α相同时，距离 P0 ⽐较近的排在前⾯。

例如上图得到的结果为P1，P2，P3，P4，P5，P6，P7，P8。

我们由⼏何知识可以知道，结果中第⼀个点 P1 和最后⼀个点 P8 ⼀定是凸包上的点。

（以上是准备步骤，以下开始求凸包）以上，我们已经知道了凸包上的第⼀个点 P0 和第⼆个点 P1，我们把它们放在栈⾥⾯。

现在从步骤3求得的那个结果⾥，把 P1 后⾯的那个点拿出来做当前点，即 P2 。

接下来开始找第三个点：4. 连接P0和栈顶的那个点，得到直线 L 。

看当前点是在直线 L 的右边还是左边。

如果在直线的右边就执⾏步骤5；如果在直线上，或者在直线的左边就执⾏步骤6。

5. 如果在右边，则栈顶的那个元素不是凸包上的点，把栈顶元素出栈。

执⾏步骤4。

6. 当前点是凸包上的点，把它压⼊栈，执⾏步骤7。

7. 检查当前的点 P2 是不是步骤3那个结果的最后⼀个元素。

是最后⼀个元素的话就结束。

如果不是的话就把 P2 后⾯那个点做当前点，返回步骤4。

最后，栈中的元素就是凸包上的点了。

以下为⽤Graham扫描法动态求解的过程： 下⾯静态求解过程1 #include<iostream>2 #include<string.h>3 #include<algorithm>4 #include<cstdio>5 #include<cmath>6using namespace std;7const int maxn=105;8const double PI=acos(-1.0);9struct node{int x,y;};10 node vex[maxn];//存⼊所有坐标点11 node stackk[maxn];//凸包中所有的点12bool cmp1(node a,node b){//按点的坐标排序13if(a.y==b.y)return a.x<b.x;//如果纵坐标相同，则按横坐标升序排14else return a.y<b.y;//否则按纵坐标升序排15 }16bool cmp2(node a,node b){//以基点为坐标原点，极⾓按升序排，这⾥可⽤atan2函数或者叉积来进⾏极⾓排序，但是⽤atan2函数来排序效率⾼时间快，不过精度⽐叉积低17double A=atan2(a.y-stackk[0].y,a.x-stackk[0].x);//返回的是原点⾄点(x,y)的⽅位⾓，即与x轴的夹⾓18double B=atan2(b.y-stackk[0].y,b.x-stackk[0].x);19if(A!=B)return A<B;//逆时针⽅向为正值，极⾓⼩的排在前⾯20else return a.x<b.x;//如果极⾓相同，则横坐标在前⾯的靠前排列21 }22int cross(node p0,node p1,node p2){//计算两个向量a、b（a=(x1,y1),b=(x2,y2)）的叉积公式：a×b=x1y2-x2y1 ===> p0p1=(x1-x0,y1-y0),p0p2=(x2-x0,y2-y0)23return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);24 }25double dis(node a,node b){//计算两点之间的距离26return sqrt((a.x-b.x)*(a.x-b.x)*1.0+(a.y-b.y)*(a.y-b.y));27 }28int main(){29int t;30while(~scanf("%d",&t)&&t){31for(int i=0;i<t;++i)//输⼊t个点32 scanf("%d%d",&vex[i].x,&vex[i].y);33if(t==1)printf("%.2f\n",0.00);//如果只有⼀个点，则周长为0.0034else if(t==2)printf("%.2f\n",dis(vex[0],vex[1]));//如果只有两个点，则周长为两个点的距离35else{36 memset(stackk,0,sizeof(stackk));//清037 sort(vex,vex+t,cmp1);//先按坐标点的位置进⾏排序38 stackk[0]=vex[0];//取出基点39 sort(vex+1,vex+t,cmp2);//将剩下的坐标点按极⾓进⾏排序，以基点为坐标原点40 stackk[1]=vex[1];//将凸包中的第⼆个点存⼊凸集中41int top=1;//当前凸包中拥有点的个数为top+142for(int i=2;i<t;++i){//不断地找外围的坐标点43while(top>0&&cross(stackk[top-1],stackk[top],vex[i])<=0)top--;//如果叉积为负数或0（0表⽰两向量共线），则弹出栈顶元素44//虽然第2个凸点显然是最外围的⼀点，但加上top>0保证了栈中⾄少有2个凸点45 stackk[++top]=vex[i];46 }47double s=0;48for(int i=1;i<=top;++i)//计算凸包的周长49 s+=dis(stackk[i-1],stackk[i]);50 s+=dis(stackk[top],vex[0]);//最后⼀个点和第⼀个点之间的距离51 printf("%.2f\n",s);52/*53 int s=0;//计算凸包的⾯积54 for(int i=1;i<=top;i++)55 s+=cross(st[i-1],st[i],e[0])/2;56*/57 }58 }59return0;60 }。

凸包问题解题报告题目：在平面上给定了N 个点，求包含这N 个点的最小凸几何体，如下：算法思路：找出输入节点中的y 值最小的点，如果有若干个y 值相同的点，选择出x 最小的点（标号为min ）从min 开始，按逆时针方向搜寻下一个点，先寻找右上方的点，要求斜率k>0，且斜率要最小，如果右上方找不到点了，再寻找左上方的点，此时要求斜率k<0，且斜率要最小，如果左上方也找不到点了，继续寻找左下方的点，此时要求斜率k>0，且斜率要最小，如果左下方也找不到满足要求的点了，则最后寻找右下方的点，直到重新找到起始的min 点，说明此次搜寻结束。

算法思路并不难，下面说一些程序运行时的技巧。

1、从上面的思路中可以看到，有四个方向要去寻找，如果分4段写，无疑是比较麻烦的，有没有什么好的办法，可以缩短代码？可以，我们可以考虑用一个循环来一次将四个方向都给搜遍：注意观察一下，假设当前节点的坐标为{ EMBED Equation.KSEE3 \* MERGEFORMAT |）（00,y x ，而被测试节点的坐标为，考虑到实际运算的情况，则四个方向分别满足如下条件即可：右上方的满足条件是：（在右侧的点的必定大于）左上方的满足条件是：（在上方的点的必定小于）左下方的满足条件是：（在左侧的点的必定小于）右下方的满足条件是：（在下方的点的必定大于）而如果第一个和第二个条件不等式的两边同时乘以1，第三个和第四个条件不等式的两边同时乘以-1，则四个不等式全都是大于的关系。

而第一个和第三个比较的是和的关系，第二个和第四个比较的是和的关系，因此对于如下循环For(int i = 0; i < 4; ++ i)表示的四个方向循环for (int j = 0; j < num; ++ j) //依次选择每个点比较的条件可以用如下一个式子表示：If(point[min][i%2]*pow(-1,i/2) > point[j][i%2]*pow(-1,i/2)){.......}由此解决了四个方向的循环问题。

实验报告课程名称：算法设计与分析实验名称：解0-1背包问题任课教师：王锦彪专业：计算机应用技术班级: 2011 学号： ****** 姓名：严焱心完成日期： 2011年11月一、实验目的：掌握动态规划、贪心算法、回溯法、分支限界法的原理，并能够按其原理编程实现解决0-1背包问题，以加深对上述方法的理解。

二、实验内容及要求：1． 要求分别用动态规划、贪心算法、回溯法和分支限界法求解0-1背包问题；2． 要求显示结果。

三、实验环境和工具：操作系统：Windows7开发工具：Eclipse3.7.1 jdk6开发语言：Java四、实验问题描述：0/1背包问题:现有n 种物品，对1<=i<=n ，第i 种物品的重量为正整数W i ，价值为正整数V i ，背包能承受的最大载重量为正整数C ，现要求找出这n 种物品的一个子集，使得子集中物品的总重量不超过C 且总价值尽量大。

动态规划算法描述: 根据问题描述，可以将其转化为如下的约束条件和目标函数：⎪⎩⎪⎨⎧≤≤∈≤∑∑==)1}(1,0{C max 11n i x x w x v ini i i ni ii寻找一个满足约束条件，并使目标函数式达到最大的解向量),......,,,(321n x x x x X =，使得C 1∑=≤n i i i x w ，而且∑=ni i i x v 1达到最大。

0-1背包问题具有最优子结构性质。

假设),......,,,(321n x x x x 是所给的问题的一个最优解，则),......,,(32n x x x 是下面问题的一个最优解：∑∑==⎪⎩⎪⎨⎧≤≤∈-≤n i i i ini i i x v n i x x w x w 2211max )2}(1,0{C 。

如果不是的话，设),......,,(32n y y y 是这个问题的一个最优解，则∑∑==>n i n i i i i i x v y v 22，且∑=≤+n i i i y w x w 211C 。