算法设计与分析实验报告实验二0-1背包年月院系：班级：学号：姓名：任课教师：成绩：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）选择单位重量价值最大的物品，在背包价值增长和背包容量消耗两者iiiiwjvwjiVjiVwjjiVjiV}),1(),,1(max{),1(),(2之间寻找平衡，即利用性价比求的目标函数最大。应用第三种贪心策略，每次从物品集合中选择单位重量价值最大的物品，如果其重量小于背包容量，就可以把它装入，并将背包容量减去该物品的重量，然后我们就面临了一个最优子问题——它同样是背包问题，只不过背包容量减少了，物品集合减少了。因此背包问题具有最优子结构性质。四.算法实现（一）动态规划法1.数据结构及函数说明intmax(inti,intj);//比较并返回两个数中的较大值intKnapSack(intw[],intv[],intx[],intn,intc);//求解背包取得的最大值2.源程序代码#include#include"stdio.h"#include#includeusingnamespacestd;//比较并返回两个数中的较大值intmax(inti,intj){if(i0;i--)//求装入背包的物品编号{if(V[i][j]>V[i-1][j]){x[i]=1;j=j-w[i];}elsex[i]=0;}returnV[n][c];}intmain(){intc,n,w[105],v[105],x[105],max;//x[]记录物品的选择情况inti,j,k=10;FILE*fp,*fp1;//定义文件指针if((fp=fopen("input.txt","r"))==NULL)//如果文件名不存在{cout<<"无法找到文件";}while(k--){clock_tstart,finish;doubletotaltime;start=clock();cout<<"请输入背包的容量：";fscanf(fp,"%d",&c);cout<
