01背包问题实验报告.pdfVIP

算法设计与分析

实验报告书

实验名称：0/1背包问题

学号：

姓名：

实验时间：2015年6月1日

《算法分析与设计》实验报告-1-

一实验目的和要求

（1）深刻掌握贪心法、动态规划法、回溯法的设计思想并能熟练运用

（2）理解这样一个观点：同样的问题可以用不同的方法来解决，一个好

的算法是反复努力和重新修正的结果。

二实验内容

（1）分别用蛮力法贪心法、动态规划法、回溯法设计0/1背包问题的算

法。

（2）分析算法随n和C变化的时间性能，随机产生参数n和C，收集算

法执行的时间

（3）讨论n和C变化时，动态规划法和回溯法的时间性能。

（4）讨论几种算法在该问题求解上的特点。

三实验环境

VC++6.0

四设计思想及实验步骤

蛮力法的设计思想和步骤

将所有排列下的背包的重量和价值都计算出来，选择重量不大于背包的总

重量下的最大价值。

贪心法的设计思想和步骤

首先计算每种物品单位重量的价值vi/wi；按单位价值对物品进行升序排

列。然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入

《算法分析与设计》实验报告-2-

背包，直到背包装满为止。

动态规划法的设计思想和步骤

令V(i,j)表示在前i个物品中能够装入容量为j的背包中的物品的最大价

值，则可以得到如下动态函数：

V（i,j）=0(i=0或j=0)

V(i,j)=V(i-1,j)jw[i]

V(i,j)=max{V(i-1,j),V(I,j-1)+v[i]}j=w[j]

按照下述方法来划分段：

第一段只装入前1个物品，确定在各种情况下的背包能够得到的最大价

值；第二阶段，只装入2个物品，确定在各种情况下的背包能够得到的最

大价值；以此类推，直到第n个阶段。最后V(n,C)便是容量为C的背包

中装入n个物品时获取到的最大价值。

回溯法的设计思想和步骤

为了避免生成那些不可能产生最佳解的问题状态，要不断的利用越约束条

件来剪掉那些实际上不可能产生所需解的节点，以减少问题额计算量。对

于n种可选物品的0/1背包问题，其解空间长度由长度为n的0-1向量

组成，可用子集数表示。在有哪些信誉好的足球投注网站解空间树时，只要其左儿子节点是一个可

行节点，有哪些信誉好的足球投注网站进入左子树，否则返回上一节点，有哪些信誉好的足球投注网站右子数。

时间测试的设计思想

蛮力法由于需要考虑每一种情况所以物品的个数不能太多，所以设计时间

测试函数在1到32的范围内随机残生物品的个数n，然后在随机产生n

《算法分析与设计》实验报告-3-

个物品每个物品的重量和价值，将背包容量设为n个物品总重量的一半，

求出最优解。重复执行背包求解过程，然后求出其平均时间消耗。

算法描述如下：

蛮力法：

输入：物品总数n，每个物品的重量w[i]和价值v[i]，背包容量C

输出：背包所装物品的最大总价值

1.求出2的n次方

2.循环i从1到m-1，

2.1求出i的二进制

2.2根据i的二进制序列，判断重量和是否小于或等于C，如果等于则

求出总价值value，

2.3如果valuemaxValue,则maxValue=value;，并把该二进制序

列T复制到S数组中以记录最优解。

贪心法：

输入：物品总数n，每个物品的重量w[i]和价值v[i]，背包容量C