《算法设计和分析实验四贪心算法求解背包问题.doc》由会员分享，可在线阅读，更多相关《算法设计和分析实验四贪心算法求解背包问题.doc（5页珍藏版）》请在三一文库上搜索。
1、实验五：贪心算法求解背包问题实验内容应用贪心算法求解离散背包问题，分析时间复杂度。有一个承重为W的背包和n个物品，它们各自的重量和价值分别是wi和vi（1=i=n），设 求这些物品中最有价值的一个子集。如果每次选择某一个物品的时候，只能全部拿走，则这一问题称为离散（0-1）背包问题；如果每次可以拿走某一物品的任意一部分，则这一问题称为连续背包问题。 算法思想 动态规划的思想： 对较小的子问题进行一次求解，并把结果记录下来，然后利用较小问题的解，求解出较大问题的解，直到求解出最大问题的解。引进一个二维数组chMAXMAX，用chij记录CH1与CH2的LCS 的长度，bij记录chij是通过哪一
2、个子问题的值求得的，以决定搜索的方向。我们是自底向上进行递推计算，那么在计算chi,j之前，chi-1j-1，chi-1j与chij-1均已计算出来。此时我们根据CH1 i = CH2j还是CH1i != CH2j，就可以计算出chij。算法length(string CH1,string CH2,int bMAXMAX)/用于构建动态数组/输入：两字符窜/输出：最长公共子序列for(i=1;i=ch1Len;i+)/二重循环求解for(int j=1;j=chij-1)/上比较大chij=chi-1j;bij=1;else/左比较大chij=chij-1;bij=-1;printCS(int
3、 bMAXMAX,string x,int i,int j)/回溯求出最长子序列输出/输入：标记数组/输出：最长子序列if(i = 0 | j = 0)/边界，返回return; if(bij = 0) printCS(b, x, i-1, j-1);/左上coutxi-1 ; else if(bij = 1) printCS(b, x, i-1, j);/上 else printCS(b, x, i, j-1);/左源程序/应用贪心算法求解离散背包问题#includeusing namespace std;#define MAX 100/结构体struct Elem double W;dou
4、ble V;double P;int number;/顺序表struct SqList Elem *elem;int length;int listsize;/构造一个空的线性顺序表void InitList_Sq(SqList &L)L.elem=(Elem *)malloc(100*sizeof(Elem);L.length=0;L.listsize=100;/*/构造背包,顺序表/*void input(SqList &L)coutL.length;for(int i=0;iL.length;i+)cout请输入第i+1L.elemi.WL.elemi.V;L.elemi.P=L.ele
5、mi.V/L.elemi.W;cout价值比为：L.elemi.Pendl;L.elemi.number=i+1;/*/插入排序由大到小/*void inser(SqList &L) Elem inserter;int index;/inserter待插入合适位置的元素,index指示插入位置 for(int pass=1;pass=0&inserter.PL.elemindex.P) /寻找插入位置L.elemindex+1=L.elemindex;index-;/指针前移，再比较L.elemindex+1=inserter;/跳出while时，找到插入位置/end of forcout按照
6、价值比由大到小排列的顺序为：;for(pass=0;passL.length;pass+)coutL.elempass.number ;coutendl;/*8/背包程序/采用贪心算法/根据价值和重量的比来实现贪心算法/*void bag(SqList L)double w,sumV=0,sumW=0;int listMAX,a=0;coutw;inser(L);for(int i=0;iL.length;i+)while(sumW+L.elemi.W=w)sumW=sumW+L.elemi.W;sumV=sumV+L.elemi.V;lista+=L.elemi.number;cout最后包
7、里的总重量为：sumWendl;cout最后包里的总价值为：sumVendl;cout放到背包中的物品的序号列表为：;for(i=0;ia;i+)coutlisti ;int main()cout贪心算法求解背包问题endl;SqList L; InitList_Sq(L);input(L);bag(L);return 0;实验结论1、 运行截图查找最长公共子序列长度时的动态规划两个for循环，时间复杂度为（）。在回溯查找时，由于每次调用至少向上或向左（或向上向左同时）移动一步，故最多调用(m + n)次就会遇到i = 0或j = 0的情况，此时开始返回。返回时与递归调用时方向相反，步数相同，故算法时间复杂度为(m + n)。