算法设计和分析实验四:贪心算法求解背包问题

算法设计和分析实验四:贪心算法求解背包问题

ID:8919260

大小:58.00 KB

页数:5页

时间:2018-04-12

算法设计和分析实验四:贪心算法求解背包问题_第1页
算法设计和分析实验四:贪心算法求解背包问题_第2页
算法设计和分析实验四:贪心算法求解背包问题_第3页
算法设计和分析实验四:贪心算法求解背包问题_第4页
算法设计和分析实验四:贪心算法求解背包问题_第5页
资源描述:

《算法设计和分析实验四:贪心算法求解背包问题》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、实验五:贪心算法求解背包问题实验内容应用贪心算法求解离散背包问题,分析时间复杂度。有一个承重为W的背包和n个物品,它们各自的重量和价值分别是wi和vi(1<=i<=n),设求这些物品中最有价值的一个子集。如果每次选择某一个物品的时候,只能全部拿走,则这一问题称为离散(0-1)背包问题;如果每次可以拿走某一物品的任意一部分,则这一问题称为连续背包问题。算法思想•动态规划的思想:–对较小的子问题进行一次求解,并把结果记录下来,然后利用较小问题的解,求解出较大问题的解,直到求解出最大问题的解。–引进一个二维数组ch[MAX][MAX],用ch[i][j]记

2、录CH1与CH2的LCS的长度,b[i][j]记录ch[i][j]是通过哪一个子问题的值求得的,以决定搜索的方向。我们是自底向上进行递推计算,那么在计算ch[i,j]之前,ch[i-1][j-1],ch[i-1][j]与ch[i][j-1]均已计算出来。此时我们根据CH1[i]=CH2[j]还是CH1[i]!=CH2[j],就可以计算出ch[i][j]。算法length(stringCH1,stringCH2,intb[MAX][MAX])//用于构建动态数组//输入:两字符窜//输出:最长公共子序列for(i=1;i<=ch1Len;i++)//二

3、重循环求解for(intj=1;j<=ch2Len;j++){if(CH1[i-1]==CH2[j-1])//相等字符{ch[i][j]=ch[i-1][j-1]+1;b[i][j]=0;}elseif(ch[i-1][j]>=ch[i][j-1])//上比较大{ch[i][j]=ch[i-1][j];b[i][j]=1;}else//左比较大{ch[i][j]=ch[i][j-1];b[i][j]=-1;}}printCS(intb[MAX][MAX],stringx,inti,intj)//回溯求出最长子序列输出//输入:标记数组//输出:最长子

4、序列if(i==0

5、

6、j==0)//边界,返回return;if(b[i][j]==0){printCS(b,x,i-1,j-1);//左上cout<usingnamespacestd;#defineMAX100//结构体structElem{doubleW;doubleV;doubleP;intnumber;};//顺序

7、表structSqList{Elem*elem;intlength;intlistsize;};//构造一个空的线性顺序表voidInitList_Sq(SqList&L){L.elem=(Elem*)malloc(100*sizeof(Elem));L.length=0;L.listsize=100;}//********************************//构造背包,顺序表//******************************voidinput(SqList&L){cout<<"请输入物品的个数:";cin>>L.leng

8、th;for(inti=0;i>L.elem[i].W>>L.elem[i].V;L.elem[i].P=L.elem[i].V/L.elem[i].W;cout<<"价值比为:"<

9、&L){Eleminserter;intindex;//inserter待插入合适位置的元素,index指示插入位置for(intpass=1;pass=0&&inserter.P>L.elem[index].P){//寻找插入位置L.elem[index+1]=L.elem[index];index--;//指针前移,再比较}L.elem[index

10、+1]=inserter;//跳出while时,找到插入位置}//endofforcout<<"按照价值比由

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。