（华电科院）算法设计与分析实验报告01背包问题 课程设计报告 ( XXXX年度第 一 学期) 名 称： 算法设计与分析 题 目 01背包问题 院 系： 信息工程 班 级： 络11k1 学 号： 学生姓名： 指导教师： 牛华为 设计周数： 1周 成 绩： 日期：XXXX年 11月 15 一、目的和要求 了解并掌握动态规划算法； 用动态规划算法解决0-1背包问题。 二、实验环境 用VC6.0软件进行编程 三、实验内容 0-1背包问题：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为c。问应如何选择装入背包中的物品，使得装入背包中的物品的总价值最大? 在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分物品i。0-1背包问题是一个特殊的整数规划问题。 四、 问题分析 在0/1背包问题中物体或者被装入背包或者不被装入背包只有两种选择。 循环变量i、j意义：前i个物品能够装入载重量为j的背包中，数组c意义：cij表示前i个物品能装入载重量为j的背包中物品的最大价值。若wij第i个物品不装入背包 ，否则若wici-1j，则记录当前最大价值，替换为第i个物品装入背包后的价值。 其c+部分代码如下： #include void knapsack(int a100100,int s100,int v100,int n,int C) for(int i=0;iai-1j) aij=vi+ai-1j-si; else aij=ai-1j; else aij=ai-1j; void outputsack(int a100100, int x100,int s100,int n,int C) for(int k=n;k=1;k-) if(akC=ak-1C) xk=0; else xk=1; C=C-sk; x1=a1C?1:0; int main() int a100100; int s100; int v100; int x100; int C,n; coutn; coutC; coutsi; coutvi; knapsack(a,s,v,n,C); outputsack(a,x,s,C,n); /max(s,v); /for( i=1;i 五、调试过程及实验结果 六、总结 01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成01背包问题求解。 实验二：贪心算法解01背包问题 一、实验目的 学习掌贪心算法法思想。 二、实验内容 用贪心法求解01背包问题，并输出问题的最优解。 问题描述：给定n种物品和一背包。物品i的重量是Wi，其价值为Vi，背包的容量是c，问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。 三、实验条件 用VC6.0软件进行编程。 四、需求分析 对于给定n种物品和一背包。在容量最大值固定的情况下，要求装入的物品价值最大化。 五、基本思想： 总是对当前的问题作最好的选择，也就是局部寻优。最后得到整体最优。总是选择单位价值最高的物品 六、代码如下： #include using namespace std; struct goodinfo float p; /物品效益 float w; /物品重量 float X; /物品该放的数量 int flag; /物品编号 ;/物品信息结构体 void Insertionsort(goodinfo goods,int n) /插入排序，按pi/wi价值收益进行排序，一般教材上按冒泡排序 int j,i; for(j=2;j goods0=goodsj; i=j-1; while (goods0.pgoodsi.p) goodsi+1=goodsi; i-; goodsi+1=goods0; /按物品效益，重量比值做升序排列 void bag(goodinfo goods,float M,int n) float cu; int i,j; for(i=1;i if(goodsi.w goodsi.X=1; cu-=goodsi.w;/确定背包新的剩余容量 else goodsi.X=0; for(j=2;j goods0=goodsj; i=j-1; while (goods0.flag goodsi+1=goodsi; i-; goodsi+1=goods0;