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

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

2、CS 的长度，bij记录chij是通过哪一个子问题的值求得的，以决定搜索的方向。我们是自底向上进行递推计算，那么在计算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<=ch2Len;j+)if(CH1i-1=CH2j-1)/相等字符chij=chi

3、-1j-1+1;bij=0;else if(chi-1j>=chij-1)/上比较大chij=chi-1j;bij=1;else/左比较大chij=chij-1;bij=-1;printCS(int bMAXMAX,string x,int i,int j)/回溯求出最长子序列输出/输入：标记数组/输出：最长子序列if(i = 0 | j = 0)/边界，返回return; if(bij = 0) printCS(b, x, i-1, j-1);/左上cout<<xi-1<<" " else if(bij = 1) printCS(b, x,

4、i-1, j);/上 else printCS(b, x, i, j-1);/左源程序/应用贪心算法求解离散背包问题#include<iostream>using namespace std;#define MAX 100/结构体struct Elem double W;double V;double P;int number;/顺序表struct SqList Elem *elem;int length;int listsize;/构造一个空的线性顺序表void InitList_Sq(SqList &L)L.elem=(Elem *)malloc(100*sizeof(

5、Elem);L.length=0;L.listsize=100;/*/构造背包,顺序表/*void input(SqList &L)cout<<"请输入物品的个数："cin>>L.length;for(int i=0;i<L.length;i+)cout<<"请输入第"<<i+1<<"个物品的重量和价值："cin>>L.elemi.W>>L.elemi.V;L.elemi.P=L.elemi.V/L.elemi.W;cout<<

6、;"价值比为："<<L.elemi.P<<endl;L.elemi.number=i+1;/*/插入排序由大到小/*void inser(SqList &L) Elem inserter;int index;/inserter待插入合适位置的元素,index指示插入位置 for(int pass=1;pass<L.length;pass+) /共比较size-1轮inserter=L.elempass;/第pass轮时,待插入的对象是apassindex=pass-1;while(index>=0&&inserte

7、r.P>L.elemindex.P) /寻找插入位置L.elemindex+1=L.elemindex;index-;/指针前移，再比较L.elemindex+1=inserter;/跳出while时，找到插入位置/end of forcout<<"按照价值比由大到小排列的顺序为："for(pass=0;pass<L.length;pass+)cout<<L.elempass.number<<" "cout<<endl;/*8/背包程序/采用贪心算法/根据价值和重量的比来实现贪心算法/*void

8、 bag(SqList L)double w,sumV=0,sumW=0;int listMAX,a=0;cout<<"请输入背包承重量W:"cin>>w;inser(L);for(int i=0;i<L.length;i+)while(sumW+L.elemi.W<=w)sumW=sumW+L.elemi.W;sumV=sumV+L.elemi.V;lista+=L.elemi.number;cout<<"最后包里的总重量为："<<sumW<<endl;cout<<"最后包里的总价值为："<<sumV<<endl;cout<<"放到背包中的物品的序号列表为："for(i=0;i<a;i+)cout<<listi<<" "int main()cout<<"贪心算法求解背包问题"<<endl;SqList L; InitList_Sq(L);input(L);bag(L);return 0;实验结论1、 运行截图查找最长公共子序列长度时