最小重量机器设计

算法分析与设计实验报告——最小重量机器设计回溯法解决一、实验目的建立算法复杂度的理论分析与实验分析的联系，深刻体会算法复杂度作为算法的好坏评价指标的本质含义。二、实验要求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表示递归深度）。①若cpd，则为不可行解，剪去相应子树，返回到i-1层继续执行。②若cw=sum，则不是最优解，剪去相应子树，返回到i-1层继续执行。③若in，则算法搜索到一个叶结点，用sum对最优解进行记录，返回到i-1层继续执行；④用for循环对部件i从m个不同的供应商购得的情况进行选择(1≤j≤m）。c.主函数调用一次Knapsack(1)即可完成整个回溯搜索过程，最终得到的sum即为所求最小总重量。五、运行结果六、实验分析与讨论计算复杂性性分析：七、实验心得通过这次试验我明白了回溯法的思想，回溯法借助想象出来的树的结构，把问题简单化，使得解问题更方便。通过剪枝函数和约束函数对于求问题的解有很大的帮助，但要把一些限制条件把剪枝函数抽象化。