算法设计背包问题.docx

《算法设计背包问题.docx》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、算法实验报告---背包问题实验目的1．掌握动态规划算法的基本思想，包括最优子结构性质和基于表格的最优值计算方法。2．熟练掌握分阶段的和递推的最优子结构分析方法。3．学会利用动态规划算法解决实际问题。问题描述：给定n种物品和一个背包。物品i的重量是wi，体积是bi，其价值为vi，背包的容量为c，容积为d。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大?在选择装入背包的物品时，对每种物品只有两个选择：装入或不装入，且不能重复装入。输入数据的第一行分别为：背包的容量c，背包的容积d，物品的个数n。接下来的n行表示n个物品的重量、体积和价值。输出为最大的总价值。问题分析:标准0-1

2、背包问题，MaxV表示前i个物品装入容量为j的背包中时所能产生的最大价值，结构体objec表示每一个可装入物品，其中w表示物品的重量，v表示物品的价值。如果某物品超过了背包的容量，则该物品一定不能放入背包，问题就变成了剩余i-1个物品装入容量为j的背包中所能产生的最大价值；如果该物品能装入背包，问题就变成i-1个物品装入容量为j-objec[i].w的背包所能产生的最大价值加上物品i的价值objec[i].v.复杂性分析时间复杂度，最好情况下为0，最坏情况下为：（abc）源程序#include#include#include#incl

3、ude#includeintV[200][200][200];intmax(inta,intb){if(a>=b)returna;elsereturnb;}intKnapSack(intn,intw[],intz[],intv[],intx[],intc,intb){inti,p,q;for(i=0;i<=n;i++)V[i][0][0]=0;for(p=0;p<=c;p++)for(q=0;q<=b;q++)V[0][p][q]=0;for(i=0;i<=n-1;i++)for(p=0;p<=c;p++)for(q=0;q<=b;q++)if

4、(p=0;i--){if(V[i][p][q]>V[i-1][p][q]){x[i]=1;p=p-w[i];q=q-z[i];}elsex[i]=0;}cout<<"选中的物品是:";for(i=0;i

5、lser+=0;}returnr;}voidmain(){intmv;intw[150];intz[150];intv[150];intx[150];intn,i;intc;intb;//背包最大容量和容积cout<<"请输入背包的最大容量:"<>c;cout<<"请输入背包的最大容积:"<>b;cout<<"输入物品数:"<>n;cout<<"请分别输入物品的重量:"<>w[i];cout<<"请分别输入物品的体积:"<>z

6、[i];cout<<"请分别输入物品的价值:"<>v[i];mv=KnapSack(n,w,z,v,x,c,b);cout<<"最大物品价值为:"<