0-1背包问题-贪心法和动态规划法求解.doc

实验四 “0-1”背包问题 实验目的与要求 熟悉C/C++语言的集成开发环境； 通过本实验加深对贪心算法、动态规划算法的理解。 实验内容: 掌握贪心算法、动态规划算法的概念和基本思想，分析并掌握“0-1”背包问题的求解方法，并分析其优缺点。 实验题 “0-1”背包问题的贪心算法 “0-1”背包问题的动态规划算法 说明：背包实例采用教材P132习题六的6-1中的描述。要求每种的算法都给出最大收益和最优解。 设有背包问题实例n=7，M=15,，(w0,w1,。。。w6)=（2,3,5,7,1,4,1），物品装入背包的收益为：（p0，p1，。。。，p6）=（10,5,15,7,6,18,3）。求这一实例的最优解和最大收益。 实验步骤 理解算法思想和问题要求； 编程实现题目要求； 上机输入和调试自己所编的程序； 验证分析实验结果； 整理出实验报告。 实验程序 // 贪心法求解 #includeiostream #includeiomanip using namespace std; //按照单位物品收益排序，传入参数单位物品收益，物品收益和物品重量的数组，运用冒泡排序 void AvgBenefitsSort(float *arry_avgp,float *arry_p,float *arry_w ); //获取最优解方法，传入参数为物品收益数组，物品重量数组，最后装载物品最优解的数组和还可以装载物品的重量 float GetBestBenifit(float *arry_p,float *arry_w,float *arry_x,float u); int main(){ float w[7]={2,3,5,7,1,4,1}; //物品重量数组 float p[7]={10,5,15,7,6,18,3}; //物品收益数组 float avgp[7]={0}; //单位毒品的收益数组 float x[7]={0}; //最后装载物品的最优解数组 const float M=15; //背包所能的载重 float ben=0; //最后的收益 AvgBenefitsSort(avgp,p,w); ben=GetBestBenifit(p,w,x,M); coutendlbenendl; //输出最后的收益 system(pause); return 0; } //按照单位物品收益排序，传入参数单位物品收益，物品收益和物品重量的数组，运用冒泡排序 void AvgBenefitsSort(float *arry_avgp,float *arry_p,float *arry_w ) { //求出物品的单位收益 for(int i=0;i7;i++) { arry_avgp[i]=arry_p[i]/arry_w[i]; } coutendl; //把求出的单位收益排序，冒泡排序法 int exchange=7; int bound=0; float temp=0; while(exchange) { bound=exchange; exchange=0; for(int i=0;ibound;i++) { if(arry_avgp[i]arry_avgp[i+1]) { //交换单位收益数组 temp=arry_avgp[i]; arry_avgp[i]=arry_avgp[i+1]; arry_avgp[i+1]=temp; //交换收益数组 temp=arry_p[i]; arry_p[i]=arry_p[i+1]; arry_p[i+1]=temp; //交换重量数组 temp=arry_w[i]; arry_w[i]=arry_w[i+1]; arry_w[i+1]=temp; exchange=i; } } } } //获取最优解方法，传入参数为物品收益数组，物品重量数组，最后装载物品最优解的数组和还可以装载物品的重量 float GetBestBenifit(float *arry_p,float *arry_w,float *arry_x,float u) { int i=0;