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

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

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

2、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++)//二重循环求解for(intj=1;j<=ch2Len;j++){if(CH1[i-1]

3、==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)//回溯求出最长子序列输出//输入：标记数组//输出：最长子序列if(i==0

4、

5、j==0)//边界，返回return;if(b[i][j]==0){printCS(b,x,i-1,j-

6、1);//左上cout<usingnamespacestd;#defineMAX100//结构体structElem{doubleW;doubleV;doubleP;intnumber;};//顺序表structSqList{Elem*elem;intlength;intlistsize;};//构造一个空的线性顺序表voidInitList_Sq(SqList&

7、L){L.elem=(Elem*)malloc(100*sizeof(Elem));L.length=0;L.listsize=100;}//********************************//构造背包,顺序表//******************************voidinput(SqList&L){cout<<"请输入物品的个数：";cin>>L.length;for(inti=0;i>L.elem[i].W>>L.elem[i].V;L.elem[i].P=L

8、.elem[i].V/L.elem[i].W;cout<<"价值比为："<

9、];//第pass轮时,待插入的对象是a[pass]index=pass-1;while(index>=0&&inserter.P>L.elem[index].P){//寻找插入位置L.elem[index+1]=L.elem[index];index--;//指针前移，再比较}L.elem[index+1]=inserter;//跳出while时，找到插入位置}//endofforcout<<"按照价值比由