(华电科院)算法设计与分析实验报告—01背包问题

《(华电科院)算法设计与分析实验报告—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(goodi

8、nfo goods[],int n)//插入排序，按pi/wi价值收益进行排序，一般教材上按冒泡排序 {  int j,i;     for(j=2;j<=n;j++)     {        goods[0]=goods[j];         i=j-1;