背包问题-贪心法和动态规划法求解

1、实验四“ 0-1背包问题一、 实验目的与要求熟悉 C/C+ 语言的集成开发环境； 通过本实验加深对贪心算法、动态规划算法的 理解。二、 实验内容 : 掌握贪心算法、动态规划算法的概念和根本思想，分析并掌握 “ 0-1 背包问题的求解 方法，并分析其优缺点。三、 实验题1. “0-1 背包问题的贪心算法2. “0-1 背包问题的动态规划算法说明：背包实例采用教材 P132 习题六的 6-1 中的描述。要求每种的算法都给出最 大收益和最优解。设有背包问题实例 n=7，M=15,，(w0,w1, 。 w6)= ( 2,3,5,7,1,4,1 ) ，物品装入 背包的收益为： ( p0，p1，。， p6

2、) =( 10,5,15,7,6,18,3 ) 。求这一实例的最优解 和最大收益。四、 实验步骤理解算法思想和问题要求； 编程实现题目要求； 上机输入和调试 自己所编的程序； 验证分析实验结果； 整理出实验报告。五、 实验程序/ 贪心法求解#include <iostream> #include "iomanip" using namespace std;获取最优解传入参数为物品收益数组，物优解的float/ 物品重量数组/ 物品收益数组/ 单位毒品的收益数组/ 最后装载物品的最优解数 组/ 背包所能的载重/ 最后的收益/ 输出最后的收float *arry_w

3、, float *arry_x, float/ 按照单位物品收益排序， 传入参数单 位物品收益， 物品收益和物品重量的 数组， 运用冒泡排序void AvgBenefitsSort( float *arry_avgp, float *arry_p, float *arry_w ); / 方法， 品重量数组，最后装载物品最 数组和还可以装载物品的重量 GetBestBenifit( float *arry_p, u);int main()float w7=2,3,5,7,1,4,1; float p7=10,5,15,7,6,18,3;float avgp7=0;float x7=0; cons

4、t float M=15;float ben=0;AvgBenefitsSort(avgp,p,w);ben=GetBestBenifit(p,w,x,M); cout<<endl<<ben<<endl;system( "pause" );return 0;/ 按照单位物品收益排序， 传入参数单位物品收益， 物品收益和物品重量的 数组， 运用冒泡排序void AvgBenefitsSort( float *arry_avgp, float *arry_p, float *arry_w )/ 求出物品的单位收益for (int i=0;i&

5、lt;7;i+) arry_avgpi=arry_pi/arry_wi;cout<<endl;/ 把求出的单位收益排序，冒泡排序法int exchange=7;int bound=0;float temp=0;while (exchange)bound=exchange;exchange=0;for (int i=0;i<bound;i+)if (arry_avgpi<arry_avgpi+1)/ 交换单位收益数组 temp=arry_avgpi;arry_avgpi=arry_avgpi+1;arry_avgpi+1=temp; / 交换收益数组 temp=arry_

6、pi;arry_pi=arry_pi+1;/arry_pi+1=temp;交换重量数组temp=arry_wi; arry_wi=arry_wi+1; arry_wi+1=temp;exchange=i;/ 获取最优解方法， 品最传入参数为物品收益数组，物品重量数组，最后装载物优解的数组和还可以装载物品的重量float GetBestBenifit( float *arry_p, float *arry_w, float *arry_x, float u)int i=0;/ 循环变量 ifloat benifit=0;/ 最后收益while (i<7)if (u-arry_wi>0

7、)arry_xi=arry_wi;/ 把当前物品重量缴入最优解数 组/ 收益增加当前物品收益u-=arry_wi;cout<<arry_xi<< " " i+;/ 背包还能载重量减去当前物品重return benifit;/ 动态规划法求解/ 返回最后收益benifit+=arry_pi;#include <>#include <> #define n 6 void DKNAPi(nt p, int w, int M, const int m); void main() int pn+1,wn+1;int M,i,j;int

8、m=1;for (i=1;i<=n;i+)m=m*2;printf( "nin put the weight and the p:");scanf( "%d %d",&wi,&pi);printf( "%d",m);printf( "n in put the max weight M:");scanf( "%d",&M);DKNAP(p,w,M,m);void DKNAPi(nt p, int w, int M, const int m)int p2m,w2m,pp

9、,ww,px;int Fn+1,pk,q,k,l,h,u,i,j,next,max,sn+1;F0=1;p21=w21=0;l=h=1;F1=next=2;for (i=1;i<n;i+) k=l; max=0;u=l;for (q=l;q<=h;q+)if (w2q+wi<=M)&&max<=w2q+wi)u=q;max=w2q+wi;for (j=l;j<=u;j+)pp=p2j+pi;ww=w2j+wi;while (k<=h&&w2k<ww)p2next=p2k;w2next=w2k;next+;k+;if (k

10、<=h&&w2k=ww)if (pp<=p2k) pp=p2k;k+;else if (pp>p2next-1)p2next=pp;w2next=ww;next+;while (k<=h&&p2k<=p2next-1) k+;while (k<=h)p2next=p2k;w2next=w2k;next=next+1;k+;l=h+1;h=next-1;Fi+1=next;for (i=1;i<next;i+)printf( "%2d%2d ",p2i,w2i);for (i=n;i>0;i-)next=Fi;next-;pp=pk=p2next;ww=w2next;while (ww+wi>M&&next>Fi-1) next=next-1;pp=p2next;ww=w2next;if (ww+wi<=M&&next>