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

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最后包里的总重量为：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循环，时间复杂度为（）。在回溯查