电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

01背包实验报告VIP免费

01背包实验报告_第1页
1/16
01背包实验报告_第2页
2/16
01背包实验报告_第3页
3/16
算法设计与分析实验报告实验二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<

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

01背包实验报告

确认删除?
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群