0-1背包(动态规划、回溯)和背包(贪心)实验报告

西安郵電學院算法设计与分析课内试验报告题目：0-1背包(动态规划、回溯)和背包(贪心)院系名称：计算机学院专业名称：软件工程专业班级：0903班学生姓名：张桥学号（8位）：04095091(23)指导教师：陈琳时间：2011年12月一.设计目的通过上机实验：深刻理解和掌握0-1背包(动态规划算法、回溯算法)和背包(贪心算法)的问题描述、算法设计思想、程序设计、算法复杂性分析、他们的区别及联系。二.设计内容1问题的描述(1)0-1背包问题给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？(2)背包问题与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1=i=n。2算法设计思想(1)0-1背包问题动态规划法：是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。设所给0-1背包问题的子问题的最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下。回溯法：在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。iiiiwjwjjimvwjimjimjim0),1(}),1(),,1(max{),(nnnwjwjvjnm00),((2)背包问题贪心算法：首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。三．测试数据及运行结果1．正常测试数据（3组）及运行结果0-1背包问题：动态规划法：回溯法：背包问题：贪心算法：四．调试情况，设计技巧及体会本次的实验大体理解和掌握0-1背包(动态规划算法、回溯算法)和背包(贪心算法)的问题描述、算法设计思想、程序设计、算法复杂性分析、他们的区别及联系。通过本次上机实验，我对0-1背包(动态规划算法、回溯算法)和背包(贪心算法)有了更为深刻的了解，利用动态规划算法、回溯算法和贪心可以将问题简化，这有助于我们在实际问题中解决一些复杂性较大的问题，提高程序的运行效率。但要注意他们的区别与不同的应用场景。五.源代码1）0-1背包：动态规划法：#includestdio.h#defineMAX20voidKnapsack(int*value,int*weight,intcolumn,intlength,int(*middle)[MAX]);voidTraceBack(int(*middle)[MAX],int*weight,intcolumn,intlength,int*x);intMax(intx,inty);intMin(intx,inty);intMin(intx,inty){returnx=y?x:y;}intMax(intx,inty){returnx=y?x:y;}voidTraceBack(int(*middle)[MAX],int*weight,intcolumn,intlength,int*x){inti;for(i=1;ilength;i++)if(middle[i][column]==middle[i+1][column])x[i]=0;else{x[i]=1;column-=weight[i];}x[length]=(middle[length][column]?1:0);}voidKnapsack(int*value,int*weight,intcolumn,intlength,int(*middle)[MAX]){inti,j,jMax=Min(weight[length]-1,column);for(j=0;j=jMax;j++)middle[length][j]=0;for(j=weight[length];j=column;j++)middle[length][j]=value[length];for(i=length-1;i1;i--){jMax=Min(weight[i]-1,column);for(j=0;j=jMax;j++)middle[i][j]=middle[i+1][j];for(j=weight[i];j=column;j++)middle[i][j]=Max(middle[i+1][j],middle[i+1][j-weight[i]]+value[i]);}middle[1][column]=middle[2][column];if(column=weight[1])middle[1][column]=Max(middle[1][column],middle[2][column-weight[1]]+value[1]);}voidmain(void){inti,length,column,count=0,weight[MAX],value[MAX],x[MAX]={0},middle[MAX][MAX]={0};printf(请输入背包总容量：\n);scanf(%d,&column);printf(请输入物品个数：\n);scanf(%d,&length);if(length1){printf(输入错误！！！\n);return;}for(i=1;i=length;i++){printf(请输入第%d个物品的重量及价值：\n,i);scanf(%d%d,weight+i,value+i);}Knapsack(value,weight,column,length,middle);TraceBack(middle,weight,column,length,x);printf(Result:\n);for(i=1;i=length;i++)if(x[i])printf(Number:%d,,i);printf(\n);}回溯法：#includestdio.h#includemalloc.h#includewindows.htypedefstructgoods{intnum;double*value;double*weight;int*location;doublecolumn;doublecurrentWeight;doublecurrentValue;doublebestValue;}GOODS;voidKnapsack(GOODS*goods,inti);doubleBound(GOODS*goods,inti);voidSwapDouble(double*m,double*n);voidSwapInt(int*m,int*n);voidSort(GOODS*goods);voidSort(GOODS*goods){inti,j;double*temp;temp=(double*)malloc(sizeof(goods-num+1));for(i=1;i=goods-num;i++)temp[i]=goods-value[i]/goods-weight[i];for(i=1;igoods-num;i++){for(j=i+1;j=goods-num;j++){if(temp[i]temp[j]){SwapDouble(&temp[i],&temp[j]);SwapDouble(&goods-weight[i],&goods-weight[j]);SwapDouble(&goods-value[i],&goods-value[j]);SwapInt(&goods-location[i],&goods-location[j]);}}}}voidSwapInt(int*m,int*n){inttemp;temp=*m;*m=*n;*n=temp;}voidSwapDouble(double*m,double*n){doubletemp;temp=*m;*m=*n;*n=temp;}doubleBound(GOODS*goods,inti){doubleleftWeight=goods-column-goods-currentWeight;doublebound=goods-currentValue;while(i=goods-num&&goods-weight[i]=leftWeight){leftWeight-=goods-weight[i];bound+=goods-value[i];i++;}if(i=goods-num)bound+=goods-value[i]*leftWeight/goods-weight[i];returnbound;}voidKnapsack(GOODS*goods,inti){if(igoods-num){goods-bestValue=goods-currentValue;return;}if(goods-currentWeight+goods-weight[i]=goods-column){goods-location[i]=1;goods-currentWeight+=goods-weight[i];goods-currentValue+=goods-value[i];Knapsack(goods,i+1);goods-currentWeight-=goods-weight[i];goods-currentValue-=goods-value[i];}if(Bound(goods,i+1)goods-bestValue){goods-location[i]=0;Knapsack(goods,i+1);}}voidmain(void){inti;doubletotalValue,totalWeight,sumWeight;GOODS*goods=NULL;totalValue=totalWeight=sumWeight=0.0;if(!(goods=(GOODS*)malloc(sizeof(GOODS)))){printf(内存分配失败\n);exit(0);}goods-currentValue=goods-currentWeight=goods-bestValue=0.0;printf(请输入背包最大重量:\n);scanf(%lf,&goods-column);printf(请输入可选物品数量:\n);scanf(%d,&goods-num);if(!(goods-value=(double*)malloc(sizeof(double)*(goods-num+1)))){printf(内存分配失败\n);exit(0);}if(!(goods-weight=(double*)malloc(sizeof(double)*(goods-num+1)))){printf(内存分配失败\n);exit(0);}if(!(goods-location=(int*)malloc(sizeof(int)*(goods-num+1)))){prin