2020-wfx-第4章 蛮力法-3-递归在蛮力法中的应用

一、实验内容：分别用蛮力法、动态规划法、回溯法和分支限界法求解0/1背包问题。

注：0/1背包问题：给定种物品和一个容量为的背包，物品的重n C i 量是，其价值为，背包问题是如何使选择装入背包内的物品，使得装i w i v 入背包中的物品的总价值最大。

其中，每种物品只有全部装入背包或不装入背包两种选择。

二、所用算法的基本思想及复杂度分析：1.蛮力法求解0/1背包问题：1）基本思想：对于有n 种可选物品的0/1背包问题，其解空间由长度为n 的0-1向量组成,可用子集数表示。

在搜索解空间树时，深度优先遍历，搜索每一个结点，无论是否可能产生最优解，都遍历至叶子结点，记录每次得到的装入总价值，然后记录遍历过的最大价值。

2）代码:#include<iostream>#include<algorithm>using namespace std;#define N 100//最多可能物体数struct goods //物品结构体{int sign;//物品序号int w;//物品重量int p;//物品价值}a[N];bool m(goods a,goods b){return (a.p/a.w)>(b.p/b.w);}int max(int a,int b){return a<b?b:a;}int n,C,bestP=0,cp=0,cw=0;int X[N],cx[N];/*蛮力法求解0/1背包问题*/int Force(int i){if(i>n-1){if(bestP<cp&&cw+a[i].w<=C){for (int k=0;k<n;k++)X[k]=cx[k];//存储最优路径bestP=cp;}return bestP;}cw=cw+a[i].w;cp=cp+a[i].p;cx[i]=1;//装入背包Force(i+1);cw=cw-a[i].w;cp=cp-a[i].p;cx[i]=0;//不装入背包Force(i+1);return bestP;}int KnapSack1(int n,goods a[],int C,int x[]){Force(0);return bestP;}int main(){goods b[N];printf("物品种数n: ");scanf("%d",&n);//输入物品种数printf("背包容量C: ");scanf("%d",&C);//输入背包容量for (int i=0;i<n;i++)//输入物品i 的重量w 及其价值v {printf("物品%d 的重量w[%d]及其价值v[%d]:",i+1,i+1,i+1);scanf("%d%d",&a[i].w,&a[i].p);b[i]=a[i];}int sum1=KnapSack1(n,a,C,X);//调用蛮力法求0/1背包问题printf("蛮力法求解0/1背包问题:\nX=[ ");for(i=0;i<n;i++)cout<<X[i]<<" ";//输出所求X[n]矩阵printf("]装入总价值%d\n",sum1);bestP=0,cp=0,cw=0;//恢复初始化}3）复杂度分析：蛮力法求解0/1背包问题的时间复杂度为：。

实验项目1：蛮力法与分治法应用1、目的与要求：实验目的：了解蛮力法和分治法的基本思想，学会运用蛮力法和分治法解决实际系统设计应用中碰到的问题。

实验要求：用蛮力法实现选择、冒泡排序，或旅行商问题、背包问题等问题（任选其中之一）。

用分治法实现合并排序或快速排序。

要求写出算法的伪代码描述，并编写程序实现之，相关算法放在函数内实现，主程序给出测试用例，要设计足够多的相关测试用例，验证程序的正确性。

注意观察程序执行结果和运行的时间。

实验报告要求给出问题定义及算法的伪代码描述，程序设计的代码，算法的测试用例及结果，并分析算法的时间效率，回答指导书中的思考题。

2、实验内容：（2）用分治法实现快速排序、合并排序算法。

本实验主要是用分治法实现合并排序，快速排序程序等。

合并排序算法描述：MergeSort ( A[0...p-1] )// input 待排序数组A[0..n-1]// output 非降序排列的数组A[0..n-1]if ( n>1 ) {//至少有2个元素Copy A[0.. n/2-1 ] to B[0.. n/2-1 ];Copy A[n/2..n-1 ] to C[0.. n/2-1 ];MergeSort ( B[0.. n/2-1 ] );MergeSort (C[0.. n/2-1 ]t);Merge (B, C, A); //复制回数组a快速排序算法描述：QuickSort ( A[1.. r ] ){if (l<r) s=Partition( A[l,r] ); // s 是分裂位置QuickSort ( A[l..s-1] ); //对左半段排序QuickSort ( A[s+1,r); //对右半段排序}Partition ( A[l..r] ){p=A[[l] ;i = l; j = r + 1;repeatedrepeated i=i+1; until A[i]> p // 将>= x的元素交换到左边区域repeated i=i+1; until A[i]> p // <= x的元素交换到右边区域Swap( A[i], A[j] )Until i>jSwap( A[i] = a[j] );Swap( A[l], A[j] )return j;要求先给出算法的伪代码，然后用C++或其他程序设计语言编写程序实现之，并设计相关的测试用例，验证程序的正确性。

算法设计与分析实验名称：用蛮力法、动态规划法和贪心法求0/1背包问题作者姓名：xxxxxxxxx完成日期：2013年9月22日星期日组的编号：28目录第一章：简介 (1)第二章：算法规范 (2)数据结构 (2)伪代码 (3)第三章：算法测试 (4)蛮力法 (4)动态规划 (5)贪心法 (5)第四章：分析讨论 (6)算法分析 (6)时间复杂度分析 (16)附录 (17)声明 (17)第一章：简介问题的描述：0/1背包问题是给定n 个重量为{w 1, w 2, … ,wn }、价值为{v 1, v 2, … ,vn }的物品和一个容量为C 的背包，求这些物品中的一个最有价值的子集，并且要能够装到背包中。

在0/1背包问题中，物品i 或者被装入背包，或者不被装入背包，设xi 表示物品i 装入背包的情况，则当xi =0时，表示物品i 没有被装入背包，xi =1时，表示物品i 被装入背包。

根据问题的要求，有如下约束条件和目标函数：于是，问题归结为寻找一个满足约束条件式1，并使目标函数式2达到最大的解向量X =(x 1, x 2, …, xn )。

背包的数据结构的设计： typedef struct object {int n;//物品的编号 int w;//物品的重量∑=ni ii x v 1max （式2）⎪⎩⎪⎨⎧≤≤∈≤∑=)1(}1,0{1n i x C x w i n i i i （式1）int v;//物品的价值}wup;wup wp[N];//物品的数组，N为物品的个数int c;//背包的总重量第二章:算法规范数据结构：0/1背包问题是给定n个重量为{w1, w2, … ,wn}、价值为{v1, v2, … ,vn}的物品和一个容量为C的背包，求这些物品中的一个最有价值的子集，并且要能够装到背包中，在0/1背包问题中，物品i 或者被装入背包，或者不被装入背包，设xi表示物品i装入背包的情况，则当xi=0时，表示物品i没有被装入背包，xi=1时，表示物品i被装入背包。

递归算法解决复杂问题的利器递归算法是计算机科学中一种强大的解决问题的工具，它可以通过将大问题分解成一个或多个相同的子问题，并通过逐步解决这些子问题来得到最终问题的解。

递归算法在解决复杂问题时具有独特的优势，本文将介绍递归算法的基本原理和应用场景，并通过具体案例分析展示递归算法的效果。

一、递归算法的基本原理递归算法的核心思想是将一个大问题分解为一个或多个相同的子问题，直到子问题变得足够简单，可以直接求解。

具体来说，递归算法包含两个要素：1. 基线条件：递归算法中需要定义一个或多个基线条件作为递归的终止条件。

当满足基线条件时，递归将停止，返回最终结果。

基线条件的设定是保证递归算法正确执行的重要因素。

2. 递归调用：在递归算法中，需要通过调用自身来解决规模较小的子问题。

递归调用通常在先解决子问题，然后再利用子问题的解来解决更大规模的问题。

使用递归算法时，需要注意避免进入无限递归的情况。

为了防止无限递归，需要保证每次递归调用能够向基线条件逼近。

二、递归算法的应用场景递归算法广泛应用于需要通过分解问题来求解的场景。

以下是几个递归算法常见的应用场景：1. 阶乘计算：阶乘是一个典型的递归计算问题，可以通过将大问题转化为规模较小的子问题来实现。

阶乘的递归定义为n! = n * (n-1)!，其中基线条件是n=1时，阶乘的结果为1。

2. 斐波那契数列：斐波那契数列是另一个典型的递归计算问题，斐波那契数列的递归定义为F(n) = F(n-1) + F(n-2)，其中基线条件是F(0)和F(1)的值为1。

通过递归调用来计算斐波那契数列可以有效地解决该问题。

3. 树结构处理：树是递归定义的数据结构，因此递归算法在处理树结构时十分常见。

通过递归遍历树的各个节点，并对每个节点进行操作，可以实现对树结构的高效处理。

三、递归算法的案例分析为了更好地理解递归算法的应用，以下将分析两个具体案例。

1. 阶乘计算假设我们需要计算5的阶乘，即求解5!的值。

算法综合实验报告一、实验内容：分别用蛮力、动态规划、贪心及分支限界法实现对0-1背包问题的求解，并至少用两个测试用例对所完成的代码进行正确性及效率关系上的验证。

二、程序设计的基本思想、原理和算法描述：1、蛮力法1.1数据结构注：结构体obj用来存放单个物品的价值和重量typedef struct obj{int w;//物品的重量int v;//物品的价值};1.2 函数组成void subset(int s[][10],int n)：用来生成子集的函数void judge(int s[][10], obj obj[],int mark[],int n,int c)：判断子集的可行性int getmax(int mark[],int n,int &flag)：求解问题的最优解void outputObj(int flag,int s[][10],int n):输出选择物品的情况 1.3 输入/输出设计本程序通过键盘进行输入、屏幕进行输出。

1.4 符号名说明1.5 算法描述算法的伪代码描述如下：输入：背包的容量c,物品的个数n,n个物品的重量 w[n],价值v[n]输出：装入背包的物品编号以及产生的最大价值1.初始化最大价值 max=0,结果子集 s=φ;2.对集合{1,2,......n}的每一个子集T，执行下述操作：2.1初始化背包的价值 v=0，背包的重量 w=0;2.2对子集t的每一个元素j2.2.1 如果w+wj<c,则 w=w+wj,v=v+vj;2.2.2 否则，转步骤2考察下一个子集；2.3如果max<v,则 max=v;s=t;3.输出子集S中的各元素2、动态规划法2.1 数据结构该程序不涉及任何数据结构2.2 函数组成int max(int i,int j);比较并返回两个数中的较大值int KnapSack (int w[],int v[],int x[],int n,int c);求解背包取得的最大值2.3 输入/输出设计本程序通过键盘进行输入、屏幕进行输出。