算法分析--0&1背包问题

《算法分析--0&1背包问题》由会员分享，可在线阅读，更多相关《算法分析--0&1背包问题（3页珍藏版）》请在金锄头文库上搜索。

1、1一、实验内容和目的实验内容：0/1 背包问题：给定 n 种物品和一个背包，物品 i 的重量是 wi，其价值为 vi，背包的容量为 C，背包问题是如何选择装入背包的物品，使得装入背包中物品的总价值最大？如果在选择装入背包的物品时，对每种物品 i 只有两种选择：装入背包或不装入背包，即不能将物品 i 装入背包多次，也不能只装入物品 i 的一部分，则称为 0/1 背包问题。实验原理：在 0/1 背包问题中，物品 i 或者被装入背包，或者不被装入背包，设 xi 表示物品 i 装入背包的情况，则当 xi=0 时，表示物品 i 没有被装入背包，x i=1 时，表示物品 i 被装入背包。根据问题的要求，有

2、如下约束条件和目标函数：(1)1(,01nixCwiin(2)iniv1ma于是，问题归结为寻找一个满足约束条件式(1)，并使目标函数式(2)达到最大值的解向量 X=( x1, x2, , xn )。可以证明 0/1 背包问题满足最优性原理。0/1 背包问题可以看作是决策一个序列( x1, x2, , xn )，对任一变量 xi 的决策是决定 xi =1 还是 xi =0。在对 xi-1 决策后，已确定了( x1, x2, , xi-1 )，在决策 xi 时，问题处于下列两种状态之一：（1）背包容量不足以装入物品 i，则 xi =0，背包不增加价值；（2）背包容量可以装入物品 i，则 xi =

3、1，背包的价值增加了 vi。这两种情况下背包价值的最大者应该是对 xi 决策后的背包价值。令 V( i, j)表示在前 i(1 i n)个物品中能够装入容量为 j(1 j C)的背包中的物品的最大值，则可以得到如下动态规划函数：(3)0),()0,(jVi(4) ),1(),(max1, iiii wjvwjVjiji实验目的：（1）深刻理解并掌握动态规划法在组合问题中的应用；（2）提高应用动态规划法设计算法的技能；实验要求：利用动态规划法设计实现求解 0/1 背包问题的算法。分析并验证算法。二、所用仪器、材料（设备名称、型号、规格等）操作系统：Microsoft Windows 7开发平台：

4、Microsoft Visual Studio 2010编程语言：C 语言三、实验方法、步骤登录 Microsoft Windows 7 操作系统打开 Visual Studio 2010 开发平台2新建 “项目”“Win32 控制台应用程序”输入项目名称“应用程序设置”勾选 “空项目”复选框右击左侧 “解决方案资源管理器”下的“源文件”“添加 ”“新建项 ”新建一个 “C+文件（.cpp） ”在新建的 .cpp 文件中输入 0/1 背包算法的程序代码调试运行记录结果完成实验报告。四、实验过程原始记录(数据、图表、计算等)源代码见实验报告所在目录下的 KnapSack.cpp，以下是 部分程序

5、代码的截图：五、实验结果（1）输出物品重量、价值和背包容量等信息：（2）调用 0/1 背包算法计算以上情况下问题的解，并输出 0/1 背包算法中的填充的 Vn+13C+1数组的值：（3）最后输出计算结果：六、分析和结论1. 此程序代码是参照教材中的 0/1 背包问题算法实现的，教材中 xn，wn，vn数组下标均从 1 开始使用，但本程序中这几个数组的下标均从 0 开始使用，故对教材中算法进行了适当修改，即凡是代码中用到这三个数组，均将引用的下标值减 1，但算法思想是完全相同的。2. 程序的不足在于，只是简单的对教材中的例子进行了模拟演示，没有尝试更多的试验数据，以验证算法的正确性与适用范围是否与设计思路相符。3. 0/1 背包算法中，第一个 for 循环的时间性能是 O(n)，第 2 个 for 循环的时间性能是O(c)，第 3 个循环是两层嵌套的 for 循环，其时间性能是 O(nC)，第 4 个 for 循环的时间性能是 O(n)，所以，该算法的时间复杂性为 O(nC)。