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

实验五：贪心算法求解背包问题实验内容应用贪心算法求解离散背包问题，分析时间复杂度。有一个承重为W的背包和n个物品，它们各自的重量和价值分别是wi和vi（1=i=n），设求这些物品中最有价值的一个子集。如果每次选择某一个物品的时候，只能全部拿走，则这一问题称为离散（0-1）背包问题；如果每次可以拿走某一物品的任意一部分，则这一问题称为连续背包问题。算法思想•动态规划的思想：–对较小的子问题进行一次求解，并把结果记录下来，然后利用较小问题的解，求解出较大问题的解，直到求解出最大问题的解。–引进一个二维数组ch[MAX][MAX]，用ch[i][j]记录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++)//二重循环求解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)//回溯求出最长子序列输出//输入：标记数组//输出：最长子序列if(i==0||j==0)//边界，返回return;if(b[i][j]==0){printCS(b,x,i-1,j-1);//左上coutx[i-1];}elseif(b[i][j]==1)printCS(b,x,i-1,j);//上elseprintCS(b,x,i,j-1);//左源程序//应用贪心算法求解离散背包问题#includeiostreamusingnamespacestd;#defineMAX100//结构体structElem{doubleW;doubleV;doubleP;intnumber;};//顺序表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请输入物品的个数：;cinL.length;for(inti=0;iL.length;i++){cout请输入第i+1个物品的重量和价值：;cinL.elem[i].WL.elem[i].V;L.elem[i].P=L.elem[i].V/L.elem[i].W;cout价值比为：L.elem[i].Pendl;L.elem[i].number=i+1;}}//*********************************//插入排序由大到小//*******************************voidinser(SqList&L){Eleminserter;intindex;//inserter待插入合适位置的元素,index指示插入位置for(intpass=1;passL.length;pass++){//共比较size-1轮inserter=L.elem[pass];//第pass轮时,待插入的对象是a[pass]index=pass-1;while(index=0&&inserter.PL.elem[index].P){//寻找插入位置L.elem[index+1]=L.elem[index];index--;//指针前移，再比较}L.elem[index+1]=inserter;//跳出while时，找到插入位置}//endofforcout按照价值比由大到小排列的顺序为：;for(pass=0;passL.length;pass++)coutL.elem[pass].number;coutendl;}//*************************************************8//背包程序//采用贪心算法//根据价值和重量的比来实现贪心算法//************************************************voidbag(SqListL){doublew,sumV=0,sumW=0;intlist[MAX],a=0;cout请输入背包承重量W:;cinw;inser(L);for(inti=0;iL.length;i++){while(sumW+L.elem[i].W=w){sumW=sumW+L.elem[i].W;sumV=sumV+L.elem[i].V;list[a++]=L.elem[i].number;}}cout最后包里的总重量为：sumWendl;cout最后包里的总价值为：sumVendl;cout放到背包中的物品的序号列表为：;for(i=0;ia;i++){coutlist[i];}}intmain(){cout贪心算法求解背包问题endl;SqListL;InitList_Sq(L);input(L);bag(L);return0;}实验结论1、运行截图查找最长公共子序列长度时的动态规划两个for循环，时间复杂度为Ｏ（ｎ＊ｎ）。在回溯查找时，由于每次调用至少向上或向左（或向上向左同时）移动一步，故最多调用(m+n)次就会遇到i=0或j=0的情况，此时开始返回。返回时与递归调用时方向相反，步数相同，故算法时间复杂度为Θ(m+n)。