欢迎来到天天文库
浏览记录
ID:40657632
大小:136.50 KB
页数:7页
时间:2019-08-05
《(华电科院)算法设计与分析实验报告—01背包问题》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
课程设计报告(2013--2014年度第一学期)名称:算法设计与分析题目0—1背包问题院系:信息工程班级:网络11k1学号:学生姓名:指导教师:牛华为设计周数:1周成绩:日期:2013年11月15 一、目的和要求了解并掌握动态规划算法;用动态规划算法解决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< using namespace std; struct goodinfo { float p; //物品效益 float w; //物品重量 float X; //物品该放的数量 int flag; //物品编号 };//物品信息结构体 void Insertionsort(goodinfo goods[],int n)//插入排序,按pi/wi价值收益进行排序,一般教材上按冒泡排序 { int j,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]; } }//按物品效益,重量比值做升序排列void bag(goodinfo goods[],float M,int n) { float cu; int i,j; for(i=1;i<=n;i++) goods[i].X=0; cu=M; //背包剩余容量 for(i=1;i>n; goods=new struct goodinfo [n+1];// cout<<"请输入背包的最大容量:"; cin>>M; cout<>goods[i].w; cout<<"请输入第"<>goods[i].p; goods[i].p=goods[i].p/goods[i].w;//得出物品的效益,重量比 cout< to run agian"< to exit"<>j;}}七、运行结果: 上述结果显示:贪心算法不是总是最优的.八、动态规划与贪心算法比较动态规划法又和贪婪算法有些一样,在动态规划中,可将一个问题的解决方案视为一系列决策的结果。不同的是,在贪婪算法中,每采用一次贪婪准则便做出一个不可撤回的决策,而在动态规划中,还要考察每个最优决策序列中是否包含一个最优子序列。
此文档下载收益归作者所有
举报原因
联系方式
详细说明
内容无法转码请点击此处