算法设计与分析实验报告实验二 0-1背包院系：班级：学号：姓名：任课教师：成绩：年月实验二 0-1背包一. 实验内容分别用编程实现动态规划算法和贪心法求0-1背包问题的最优解，分析比较两种算法的时间复杂度并验证分析结果二．实验目的1、掌握动态规划算法和贪心法解决问题的一般步骤，学会使用动态规划和贪心法解决实际问题；2、理解动态规划算法和贪心法的异同及各自的适用范围。
三. 算法描述1、动态规划法01背包问题的状态转换公式为： （1） V(i, 0)= V(0, j)=0（2） 公式表明：把前面i 个物品装入容量为0的背包和把0个物品装入容量为j 的背包，得到的价值均为0。
如果第i 个物品的重量大于背包的容量，则装入前i 个物品得到的最大价值和装入前i -1个物品得到的最大价值是相同的，即物品i 不能装入背包；如果第i 个物品的重量小于背包的容量，则会有以下两种情况：（1）如果把第i 个物品装入背包，则背包中物品的价值等于把前i -1个物品装入容量为j -wi 的背包中的价值加上第i 个物品的价值vi ；（2）如果第i 个物品没有装入背包，则背包中物品的价值就等于把前i -1个物品装入容量为j 的背包中所取得的价值。
显然，取二者中价值较大者作为把前i 个物品装入容量为j 的背包中的最优解。
2、贪心法背包问题至少有三种看似合理的贪心策略：（1）选择重量最轻的物品，因为这可以装入尽可能多的物品，从而增加背包的总价值。
但是，虽然每一步选择使背包的容量消耗得慢了，但背包的价值却没能保证迅速增长，从而不能保证目标函数达到最大。
（2）选择价值最大的物品，因为这可以尽可能快地增加背包的总价值。
但是，虽然每一步选择获得了背包价值的极大增长，但背包容量却可能消耗得太快，使得装入背包的物品个数减少，从而不能保证目标函数达到最大。
（3）选择单位重量价值最大的物品，在背包价值增长和背包容量消耗两者⎩⎨⎧>+---<-=i i i i wj v w j i V j i V w j j i V j i V }),1(),,1(max{),1(),(之间寻找平衡，即利用性价比求的目标函数最大。
应用第三种贪心策略，每次从物品集合中选择单位重量价值最大的物品，如果其重量小于背包容量，就可以把它装入，并将背包容量减去该物品的重量，然后我们就面临了一个最优子问题——它同样是背包问题，只不过背包容量减少了，物品集合减少了。
因此背包问题具有最优子结构性质。
四.算法实现（一）动态规划法1.数据结构及函数说明int max(int i,int j);//比较并返回两个数中的较大值int KnapSack (int w[],int v[],int x[],int n,int c);//求解背包取得的最大值2.源程序代码#include<iostream>#include "stdio.h"#include <stdlib.h>#include<time.h>using namespace std;//比较并返回两个数中的较大值int max(int i,int j){if(i<j)return j;elsereturn i;}//求解背包取得的最大值int KnapSack (int w[],int v[],int x[],int n,int c){int i,j,V[105][1005]={0};for(i=0;i<=n;i++)//初始化第0列V[i][0]=0;for(j=0;j<=c;j++)//初始化第0行V[0][j]=0;for(i=1;i<=n;i++)//计算第i行，进行第i次迭代{for(j=1;j<=c;j++){if(j<w[i])V[i][j]=V[i-1][j];elseV[i][j]=max(V[i-1][j],V[i-1][j-w[i]]+v[i]);}}for(j=c,i=n;i>0;i--)//求装入背包的物品编号{if(V[i][j]>V[i-1][j]){x[i]=1;j=j-w[i];}else x[i]=0;}return V[n][c];}int main(){int c,n,w[105],v[105],x[105],max;//x[]记录物品的选择情况int i,j,k=10;FILE *fp,*fp1;//定义文件指针if((fp=fopen("input.txt","r"))==NULL)//如果文件名不存在{cout<<"无法找到文件";}while(k--){clock_t start,finish;double totaltime;start=clock();cout<<"请输入背包的容量：";fscanf(fp,"%d",&c);cout << c <<"\n";cout<<"请输入物品的个数：";fscanf(fp,"%d",&n);cout << n <<"\n";cout<<"请分别输入物品的重量：";for(i=1;i<=n;i++){fscanf(fp,"%d",&w[i]);cout << w[i] <<" ";}cout<<endl;cout<<"请分别输入物品的价值：";for(j=1;j<=n;j++){fscanf(fp,"%d",&v[j]);cout << v[j] <<" ";}max=KnapSack(w,v,x,n,c);cout<<endl;cout<<"装入背包的物品编号为："<<endl;for(i=1;i<=n;i++){if(x[i]==1)cout<<i<<" ";}cout<<endl;cout<<"背包可容纳的最大价值为："<<max<<endl;finish=clock();totaltime=(double)(finish-start)/CLOCKS_PER_SEC;cout<<"\n此程序的运行时间为"<<totaltime<<"秒"<<endl;cout<<"-----------------------------------------"<<endl;}}（二）贪心法1.数据结构及函数说明struct good//表示物品的结构体{int value;//价值int weight;//重量double ratio;//价值与重量的比};bool bigger(good a,good b);//按比较物品的价值与重量比和质量选择较大的2.源程序代码#include<iostream>#include<algorithm>#include "stdio.h"#include <stdlib.h>#include<time.h>using namespace std;struct good//表示物品的结构体{int value;//价值int weight;//重量double ratio;//价值与重量的比};good a[2000];bool bigger(good a,good b){if(a.ratio==b.ratio)return a.weight<b.weight;else return a.ratio>b.ratio;}int main(){double s,total;int c,i,n,k=10;FILE *fp;//定义文件指针if((fp=fopen("input.txt","r"))==NULL)//如果文件名不存在{cout<<"无法找到文件";}while(k--){clock_t start,finish;double totaltime;start=clock();cout<<"请输入背包的容量：";fscanf(fp,"%d",&c);cout << c <<"\n";cout<<"请输入物品的个数：";fscanf(fp,"%d",&n);cout << n <<"\n";cout<<"请分别输入物品的重量：";for (i=0;i<n;i++){fscanf(fp,"%d",&a[i].weight);cout << a[i].weight <<" ";}cout<<endl;cout<<"请分别输入物品的价值：";for (i=0;i<n;i++){fscanf(fp,"%d",&a[i].value);cout << a[i].value <<" ";a[i].ratio=a[i].value/a[i].weight;}cout<<endl;sort(a,a+n,bigger);//调用sort排序函数，按照价值与重量比和质量排序贪心s=0;//包内现存货品的重量total=0;//包内现存货品总价值cout<<"装入背包的物品编号为："<<endl;for (i=0;i<n;i++){if(s+a[i].weight<=c){cout<<n-i<<" ";total+=a[i].value;s+=a[i].weight;}}cout<<endl;cout<<"背包可容纳的最大价值为："<<total<<endl;finish=clock();totaltime=(double)(finish-start)/CLOCKS_PER_SEC;cout<<"\n此程序的运行时间为"<<totaltime<<"秒"<<endl;cout<<"-----------------------------------------"<<endl;}return 0;}五．程序运行结果1、动态规划法2、贪心法六．实验结果分析整理实验结果可以得到下表比较动态规划法和贪心法：通过上表，我们可以看出当背包容量不是很大，物品个数不是很多的时候，动态规法和贪心法的时间开销没有太大差距；当容量和物品个数增大时，动态规划法所用的时间增长远大于贪心法。