算法设计与分析试验报告01背包问题

1、算法设计分析实验报告课程名称：计算机算法设计分析专 业：班 级：学 号：姓 名： 指导教师:一、问题的提出问题描述：给定n种物品和一个背包。物品i的重量是wi,体积是bi ,其价 值为vi ,背包的容量为c,容积为d。问应如何选择装入背包中的物 品，使得装入背包中物品的总价值最大 ？在选择装入背包的物品时，对每种物品只有两个选择：即装入或 不装入。不能重复装入，也不能只装入部分的物品i。要求：试设计一个解决此问题的动态规划算法，并分析算法的计算复杂 性。二、算法的基本思想该问题具有最优子结构特征。标准 0-1背包问题，MaxV表示前i 个物品装入容量为j的背包中时所能产生的最大价值，结构体 o

2、bjec 表示每一个可装入物品，其中w表示物品的重量，v表示物品的价值。 如果某物品超过了背包的容量，则该物品一定不能放入背包，问题就 变成了剩余i-1个物品装入容量为j的背包中所能产生的最大价值； 如果该物品能装入背包，问题就变成i-1个物品装入容量为 j-objeci.w 的背包所能产生的最大价值加上物品i的价值objeci.v三、算法的程序实现#include using namespace std;int V 200200200;int max(int a,int b)if(a=b) return a;else return b;int KnapSack(int n,int w,int

3、 z,int v,int x,int c,int b) int i,p,q;for(i=0;i=n;i+)Vi00=0;for(p=0;p=c;p+)for (q=0;q=b;q+)V0pq=0;for(i=0;i=n-1;i+)for(p=0;p=c;p+)for(q=0;q=b;q+)if(pwi&q=0;i-)if(VipqVi-1pq)xi=1;p=p-wi; q=q-zi; elsexi=0;COUtVV”选中的物品是:； for(i=0;in;i+) cout xi;coutendl;int r=0;for(i=0;in;i+)(if(xi=1) r+=vi;elser+=0;)r

4、eturn r;)void main()(int mv;int w150;int z150;int v150;int x150;int n,i;int c;int b;/背包最大容量和容积coutvv”请输入背包的最大容量：endl;cinc;coutvv”请输入背包的最大容积：endl;cinb;coutvv”输入物品数：endl;cinn;coutvv”请分别输入物品的重量:endl;for(i=0;in;i+)cinwi;coutvv”请分别输入物品的体积:endl;for(i=0;izi;cout请分别输入物品的价值:endl;for(i=0;ivi;mv=KnapSack(n,w,z,v,x,c,b);cout最大物品价值为：mvendl;四、算法的复杂度分析时间复杂度为O(n)。五、算法运行结果及分析(截屏)硒“1：八二我隹幽Drbug端占国苜折音包牙筋寸言&二多输入背包国最大容袒:1OD输入物品城：%分别输入他不的里量:5它9请与则输入牧品的休抵%藕嵋人物品的枷值:g g gI耙微嘉？0Ftbss any key to cantinu.5.输入数据的第一行分别为：背包的容量 c,背包的容积d,物品的个数n。接下来的n行表示n个物品的重量、体积和价值。输出为最 大的总价值。六、结束语包括最优子结构性质1