欢迎来到天天文库
浏览记录
ID:40657632
大小:136.50 KB
页数:7页
时间:2019-08-05
《(华电科院)算法设计与分析实验报告—01背包问题》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、课程设计报告(2013--2014年度第一学期)名称:算法设计与分析题目0—1背包问题院系:信息工程班级:网络11k1学号:学生姓名:指导教师:牛华为设计周数:1周成绩:日期:2013年11月15一、目的和要求了解并掌握动态规划算法;用动态规划算法解决0-1背包问题。二、实验环境用VC6.0软件进行编程三、实验内容0-1背包问题:给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包的容量为c。问应如何选择装入背包中的物品,使得装入背包中的物品的总价值最大?在选择装入背包的物品时,对每种物品i只有两种选择,即装入背包或
2、不装入背包。不能将物品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++部分代码如下:#include<
3、iostream.h>voidknapsack(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]
4、[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<<"请输入背包
5、的总容量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<6、dl;return0;}五、调试过程及实验结果六、总结01背包问题是最基本的背包问题,它包含了背包问题中设计状态、方程的最基本思想,另外,别的类型的背包问题往往也可以转换成01背包问题求解。实验二:贪心算法解0—1背包问题一、实验目的学习掌贪心算法法思想。二、实验内容用贪心法求解0—1背包问题,并输出问题的最优解。问题描述:给定n种物品和一背包。物品i的重量是Wi,其价值为Vi,背包的容量是c,问应如何选择装入背包中的物品,使得装入背包中物品的总价值最大。三、实验条件用VC6.0软件进行编程。四、需求分析对于给定n种物品和一7、背包。在容量最大值固定的情况下,要求装入的物品价值最大化。五、基本思想:总是对当前的问题作最好的选择,也就是局部寻优。最后得到整体最优。总是选择单位价值最高的物品六、代码如下: #include using namespace std; struct goodinfo { float p; //物品效益 float w; //物品重量 float X; //物品该放的数量 int flag; //物品编号 };//物品信息结构体 void Insertionsort(goodi8、nfo goods[],int n)//插入排序,按pi/wi价值收益进行排序,一般教材上按冒泡排序 { int j,i; for(j=2;j<=n;j++) { goods[0]=goods[j]; i=j-1;
6、dl;return0;}五、调试过程及实验结果六、总结01背包问题是最基本的背包问题,它包含了背包问题中设计状态、方程的最基本思想,另外,别的类型的背包问题往往也可以转换成01背包问题求解。实验二:贪心算法解0—1背包问题一、实验目的学习掌贪心算法法思想。二、实验内容用贪心法求解0—1背包问题,并输出问题的最优解。问题描述:给定n种物品和一背包。物品i的重量是Wi,其价值为Vi,背包的容量是c,问应如何选择装入背包中的物品,使得装入背包中物品的总价值最大。三、实验条件用VC6.0软件进行编程。四、需求分析对于给定n种物品和一
7、背包。在容量最大值固定的情况下,要求装入的物品价值最大化。五、基本思想:总是对当前的问题作最好的选择,也就是局部寻优。最后得到整体最优。总是选择单位价值最高的物品六、代码如下: #include using namespace std; struct goodinfo { float p; //物品效益 float w; //物品重量 float X; //物品该放的数量 int flag; //物品编号 };//物品信息结构体 void Insertionsort(goodi
8、nfo goods[],int n)//插入排序,按pi/wi价值收益进行排序,一般教材上按冒泡排序 { int j,i; for(j=2;j<=n;j++) { goods[0]=goods[j]; i=j-1;
此文档下载收益归作者所有