机器设计问题。某机器由n个部件组成，每一个部件可从m个供应商那里购得。设Wij是从供应商j那里购得的零件i的重量，Cij为该零件的成本。试设计一个回溯算法，给出总成本不超过c的最小重量机器设计，并分析算法的复杂度。

### 回答1：
这是一个经典的组合优化问题，可以使用回溯算法解决。具体步骤如下：

1. 定义一个变量cost，表示当前机器的成本；定义一个变量weight，表示当前机器的总重量。

2. 从第一个部件开始，遍历每个供应商，如果购买该部件的成本不超过剩余的成本限制c，就将该部件加入机器，同时更新cost和weight，并递归处理下一个部件。

3. 如果当前的机器成本超过了c，或者已经遍历完了所有部件，就记录当前机器的重量和成本，并回溯到上一个部件，继续遍历其他的供应商。

4. 遍历完所有的部件后，从记录的所有机器中选择总成本不超过c的最小重量机器。

算法的复杂度为O(nm^(n-1))，因为每个部件都有m个供应商可选，共有n个部件，所以总的搜索空间为m^n，但在实际情况中，很多机器方案都可以被排除，所以算法的实际运行时间取决于机器设计的具体情况。

### 回答2：
回溯算法是一种穷举搜索的算法，在解决机器设计问题时可以通过回溯算法找到总成本不超过c的最小重量机器设计。

具体算法如下：
1. 定义一个函数backtrack，参数包括当前正在选择的部件下标i、当前选择的供应商下标j、已选择的部件重量sum_weight、已选择的部件成本sum_cost以及总成本不超过c的标志cost_exceed。初始调用backtrack(0, 0, 0, 0, False)。
2. 首先判断是否已经选择了所有的部件，如果是，则判断当前选择的机器设计是否满足总成本不超过c的条件。如果是，更新最小重量和最小成本，并返回。如果否，直接返回。
3. 如果当前部件还没有选择完，遍历所有可能的供应商，选择其中一个供应商，并更新sum_weight和sum_cost。
4. 继续调用backtrack函数，传入下一个待选择的部件下标i+1，已选择的部件重量sum_weight，已选择的部件成本sum_cost，以及总成本不超过c的标志。
5. 在回溯时，需要将sum_weight和sum_cost恢复到回溯前的状态，以便选择其他的供应商。

算法的复杂度分析：
该算法的复杂度是指数级别的，因为需要遍历所有可能的情况。每个部件都有m个供应商可选，总共有n个部件，所以遍历的次数为m^n。因此，该算法的时间复杂度为O(m^n)，其中m是供应商的数量，n是部件的数量。

### 回答3：
在解决这个机器设计问题时，可以使用回溯算法。可以将该问题抽象为一个决策树，每个节点表示选择某个供应商提供的某个部件。使用回溯算法就是在决策树的搜索过程中按照一定的规则进行剪枝，从而找到满足条件的最优解。

具体步骤如下：

1. 初始化最小重量为无穷大，当前重量为0，当前成本为0，依次遍历n个部件。对于每个部件，遍历m个供应商。
2. 在每个供应商上进行选择，将部件的重量累加到当前重量，将部件的成本累加到当前成本。
3. 若当前成本超过限制c，则剪枝返回上一层。
4. 若当前成本小于等于限制c，并且当前重量小于最小重量，则更新最小重量。
5. 继续遍历下一个部件，直到遍历完所有部件。
6. 返回最小重量作为最终的最小重量机器设计。

该回溯算法的复杂度分析如下：

1. 对于每个部件，都需要遍历m个供应商，所以时间复杂度为O(m^n)。
2. 在遍历每个供应商时，需要更新当前重量和当前成本，以及进行剪枝操作。这些操作的时间复杂度是常数级别的。
3. 回溯算法是一种递归算法，需要使用系统栈来保存每一层的状态，所以空间复杂度为O(n)。

综上所述，该回溯算法的时间复杂度为O(m^n)，空间复杂度为O(n)。