算法分析与设计实验报告实验：0/1背包问题实验目的与要求：熟悉C/C++语言的集成开发环境；通过本实验加深对贪心算法、动态规划和回溯算法的理解。实验内容：掌握贪心算法、动态规划和回溯算法的概念和基本思想，分析并掌握"0-1"背包问题的三种算法，并分析其优缺点。实验题：有五个物品，其重量分别为（3,2,1,4,5），物品的价值分别为（25,20,15,40,50），背包容量为6，写出求解过程。"0-1"背包问题的贪心算法"0-1"背包问题的动态规划算法"0-1"背包问题的回溯算法实验步骤：1.理解算法思想和问题要求；2.编程实现题目要求；3.上机输入和调试自己所编的程序；4.验证分析实验结果；5.整理出实验报告。实验程序："0-1"背包问题的贪心算法#include<iostream>usingnamespacestd;intmain(){inti,j,a,b,Cr=6,W=0,V=0;floatper[20];intw[]={3,2,1,4,5},v[]={25,20,15,40,50};cout<<"物品重量为：";for(i=0;i<5;i++){cout<<w[i]<<",";}cout<<endl<<"物品价值为：";for(i=0;i<5;i++){cout<<v[i]<<",";}//按照价值大小降序排序for(i=4;i>=0;i--){for(j=0;j<i;j++)if(v[i]>v[j]){a=v[i];v[i]=v[j];v[j]=a;b=w[i];w[i]=w[j];w[j]=b;}}cout<<endl<<"方法一，价值最大原则："<<endl<<"按价值大小排序后："<<endl<<"物品重量为：";for(i=0;i<5;i++){cout<<w[i]<<",";}cout<<endl<<"物品价值为：";for(i=0;i<5;i++){cout<<v[i]<<",";}cout<<endl<<"放入背包的物品为：";//把物品按要求放入背包for(i=0;i<5;i++){while(Cr>=w[i]&&Cr>=0){W=W+w[i];Cr=Cr-w[i];V=V+v[i];a=i;cout<<w[a]<<",";}}cout<<endl<<"结果为：背包重量为："<<W<<",背包价值为："<<V<<endl;cout<<endl<<"方法二，重量最轻原则："<<endl<<"按重量大小排序后："<<endl<<"物品重量为：";//按照重量大小升序排序，for(i=4;i>=0;i--){for(j=0;j<i;j++)if(v[i]<v[j]){a=v[i];v[i]=v[j];v[j]=a;b=w[i];w[i]=w[j];w[j]=b;}}for(i=0;i<5;i++){cout<<w[i]<<",";}cout<<endl<<"物品价值为：";for(i=0;i<5;i++){cout<<v[i]<<",";}cout<<endl<<"放入背包的物品为：";Cr=6,W=0,V=0;//把物品按要求放入背包for(i=0;i<5;i++){if(Cr>=w[i]&&Cr>=0){W=W+w[i];Cr=Cr-w[i];V=V+v[i];a=i;cout<<w[a]<<",";}}cout<<endl<<"结果为：背包重量为："<<W<<",背包价值为："<<V<<endl;cout<<endl<<"方法三，单位重量价值最大原则："<<endl<<"按单位重量价值大小排序后："<<endl<<"物品重量为：";for(i=0;i<5;i++){per[i]=v[i]/w[i];}//如果单位重量价值相等，按照重量大小降序排序for(i=4;i>=0;i--){for(j=0;j<i;j++)if(per[i]==per[j]&&w[i]>w[j]){a=v[i];v[i]=v[j];v[j]=a;