六、实验分析与讨论 贪心法的基本思路：
——从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。 该算法存在问题：
1. 不能保证求得的最后解是最佳的； 2. 不能用来求最大或最小解问题；
3. 只能求满足某些约束条件的可行解的范围。 实现该算法的过程：
1.Begin 从问题的某一初始解出发； 2．while 能朝给定总目标前进一步 do 3.求出可行解的一个解元素；
4.由所有解元素组合成问题的一个可行解
七、实验心得
贪心算法通过一系列的选择来得知问题的解，它所做的每一个选择都是当前状态下局部最好选择，即贪心选择。通过背包问题的解决，进一步掌握了贪心算法的思想，并能在解问题时灵活运用。
15
指导教师对实验报告的评语
成绩：
指导教师签字：
年 月 日
16
实验五：最小重量机器设计问题（回溯法）
一、 实验目的
建立算法复杂度的理论分析与实验分析的联系，深刻体会算法复杂度作为算法的好坏评价指标的本质含义。 二、 实验要求
1、 用c++语言实现最小重量机器设计的回溯算法。 2、 分析算法的计算复杂性 三、 实验原理
首先，应该明确的确定问题的解空间。确定了解空间的组织结构后，发从开始节点（根节点）出发，以深度优先方式搜索整个解空间。这个开始结点成为活结点，同时也成为当前的扩展结点。在当前的扩展结点处，向纵深方向搜索移至一个新的结点。这个新结点成为新的活结点，并成为新的扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点成为死结点。此时，应往回移动（回溯）至最近的活结点，并使这个活结点成为当前的扩展结点。回溯以这种工作方式递归的在解空间中搜索，直至找到所要求的解或解空间中已无活结点为止。
四、 实验过程(步骤)
由于题目已经给出总价格的上限，因此算法通过使用回溯来选择合适的机器使得在总价格不超过d时得到的机器重量最小。首先初始化当前价格cp=0,当前重量cw=0,此外，还要设置一个变量sum表示选择机器的总重量，初始化其为每个部件从1号供应商购买的重量。在循环选择i号机器时，判断从j号供应商购买机器后的价格是否大于总价格，如果不大于则选择，否则不选，继续选择下一供应商进行判断。在得到一个合适的供应商后，继续选择下一机器的供应商，从第一个选到最后一个供应商。当所有机器选择结束后，判断得到的总重量是否比之前的sum小，如果小就赋给sum，然后从这一步开始，回溯到上一机器，选择下一合适供应商，继续搜索可行解，直到将整个排列树搜索完毕。这样，最终得到的sum即为最优解。
数据说明：
N：零件数量 m：不同的零件商
W[][]:是从供应商j处购得的部件i的重量 c[][]：相应的价值 算法设计：
a.部件有n个，供应商有m个，分别用w[i][j]和c[i][j]存储从供应商j 处购得的部件i的重量和相应价格，d为总价格的上限。
b.用递归函数backtrack(i)来实现回溯法搜索排列树（形式参数i表示递归深度）。 ① 若cp>d，则为不可行解，剪去相应子树，返回到i-1层继续执行。 ② 若cw>=sum，则不是最优解，剪去相应子树，返回到i-1层继续执行。 ③ 若i>n，则算法搜索到一个叶结点，用sum对最优解进行记录，返回到i-1层继续执行； ④ 用for循环对部件i从m个不同的供应商购得的情况进行选择(1≤j≤m）。
c.主函数调用一次Knapsack(1)即可完成整个回溯搜索过程，最终得到的sum即为所求最小总重量。
五、 运行结果
17
六、实验心得
通过这次试验我明白了回溯法的思想，回溯法借助想象出来的树的结构，把问题简单化，使得解问题更方便。通过剪枝函数和约束函数对于求问题的解有很大的帮助，但要把一些限制条件把剪枝函数抽象化。
18
指导教师对实验报告的评语
成绩：
指导教师签字：
年 月 日
19