算法设计与分析课程设计报告VIP免费

算法设计与分析课程设计报告一、目的和要求了解并掌握动态规划算法；用动态规划算法解决0-1背包问题。二、实验环境用VC6.0软件进行编程三、实验内容0-1背包问题：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为c。问应如何选择装入背包中的物品，使得装入背包中的物品的总价值最大?在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分物品i。0-1背包问题是一个特殊的整数规划问题。四、问题分析在0/1背包问题中物体或者被装入背包或者不被装入背包只有两种选择。循环变量i、j意义：前i个物品能够装入载重量为j的背包中，数组c意义：c[i][j]表示前i个物品能装入载重量为j的背包中物品的最大价值。若w[i]>j第i个物品不装入背包，否则若w[i]<=j且第i个物品装入背包后的价值>c[i-1][j]，则记录当前最大价值，替换为第i个物品装入背包后的价值。其c++部分代码如下：#includevoidknapsack(inta[100][100],ints[100],intv[100],intn,intC){for(inti=0;i<=C;i++){a[0][i]=0;}for(i=1;i<=n;i++){a[i][0]=0;for(intj=1;j<=C;j++){if(s[i]<=j){if(v[i]+a[i-1][j-s[i]]>a[i-1][j])a[i][j]=v[i]+a[i-1][j-s[i]];elsea[i][j]=a[i-1][j];}elsea[i][j]=a[i-1][j];}}}voidoutputsack(inta[100][100],intx[100],ints[100],intn,intC){for(intk=n;k>=1;k--){if(a[k][C]=a[k-1][C])x[k]=0;else{x[k]=1;C=C-s[k];}}x[1]=a[1][C]?1:0;}intmain(){inta[100][100];ints[100];intv[100];intx[100];intC,n;cout<<"请输入物品的总个数n:"<>n;cout<<"请输入背包的总容量C:"<>C;cout<<"请依次输入物品的体积s[i]:"<>s[i];}cout<<"请对应输入物品的价值v[i]:"<>v[i];}knapsack(a,s,v,n,C);outputsack(a,x,s,C,n);//max(s,v);//for(i=1;i<=n;i++)//cout<usingnamespacestd;structgoodinfo{floatp;//物品效益floatw;//物品重量floatX;//物品该放的数量intflag;//物品编号};//物品信息结构体voidInsertionsort(goodinfogoods[],intn)//插入排序，按pi/wi价值收益进行排序，一般教材上按冒泡排序{intj,i;for(j=2;j<=n;j++){goods[0]=goods[j];i=j-1;while(goods[0].p>goods[i].p){goods[i+1]=goods[i];i--;}goods[i+1]=goods[0];}}//按物品效益，重量比值做升序排列voidbag(goodinfogoods[],floatM,intn){floatcu;inti,j;for(i=1;i<=n;i++)goods[i].X=0;cu=M;//背包剩余容量for(i=1;i