最小重量机器设计问题

问题描述

设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设wij是从供应商j处够来的部件i的重量，cij是相应的价格。
试设计一个算法，给出总价格不超过c的最小重量机器设计。

算法设计：对于给定的机器部件重量和机器部件价格，计算总价值不超过d的最小重量机器设计。

数据输入：第一行由3个正整数n，m，d。接下来的2n行，每行m个数。前n行是c，后n行是w。

结果输出:将计算的最小重量及每个部件的供应商输出。

输入：             输出：
3 3 4             4
1 2 3             1 3 1
3 2 1
2 2 2 
1 2 3
3 2 1
2 2 2

算法描述

由于题目已经给出总价格的上限，因此算法通过使用回溯算法来选择合适的机器使得在总价格不超过d时得到的机器重量最小。

首先初始化当前花费cc = 0,当前重量cw = 0。此外，还要设置一个变量bestw表示选择零件的最小重量，初始化其为无穷大。在循环选择i号机器时，判断从j号供应商购买机器后的价格是否大于总价格，如果不大于则选择，否则不选，继续选择下一供应商进行判断。在得到一个合适的供应商后，继续选择下一机器的供应商，从第一个选到最后一个供应商。当所有机器选择结束后，判断得到的总重量是否比之前的bestw小，如果小就赋给bestw，然后从这一步开始，回溯到上一机器，选择下一合适供应商，继续搜索可行解，直到将整个排列树搜索完毕。这样，最终得到的bestw即为最优解。

考虑到算法的时间复杂度，还可以加上一个剪枝条件，即在每次选择某一机器时，再判断选择后的重量是否已经大于之前的bestw或选择后的花费已经大于d。如果大于就没必要继续搜索了，因为得到的肯定不是最优解。
a.部件有n个，供应商有m个，分别用二位数组c和w存储从供应商j 处购得的部件i的价格和重量，d为总价格的上限。
b.用递归函数backTrack(i)来实现回溯法搜索排列树（参数i表示排列树深度，也表示第i号零件）。
① 若cc>d，则为不可行解，剪去相应子树，返回到i-1层继续执行。
② 若cw>=bestw，则不是最优解，剪去相应子树，返回到i-1层继续执行。
③ 若i>n，则算法搜索到一个叶结点，用bestw对最优解进行记录，返回到i-1层继续执行；
④ 用for循环对部件i从m个不同的供应商购得的情况进行选择(0≤j<m）。
c.主函数调用一次backTrack(0)即可完成整个回溯搜索过程，最终得到的bestw即为所求最小总重量。

关键代码

	int n;//n种部件
    int m;//m个供应商
    int d;//总价格不超过
    int[][] c;
    int[][] w;
    int[] x;//当前解
    int[] bestx;//最优解
    int cw;//当前重量
    int cc;//当前价格
    int bestw;//最优重量	
	public void backTrace(int i) {
        if (i == n) {
            if (cw < bestw) {
                for (int j = 0; j < n; j++) {
                    if (x[j] == -1) {
                        //这个x不是解
                        return;
                    }
                }
                for (int j = 0; j < n; j++) {
                    bestx[j] = x[j];
                }
                bestw = cw;
            }
            return;
        }
        for (int k = 1; k <= m; k++) {
            //此路不通
            if (cc + c[i][k] > d || cw + w[i][k] > bestw) {
                continue;
            }
            cc += c[i][k];
            cw += w[i][k];
            x[i] = k;
            backTrace(i + 1);
            cc -= c[i][k];
            cw -= w[i][k];
            x[i] = -1;
        }
    }

结果分析

输入：

3 3 4
1 2 3
3 2 1
2 2 2
1 2 3
3 2 1
2 2 2

输出

4

1 3 1

输入：

3 3 7
1 2 3
5 4 2
2 1 2
1 2 3
3 2 1
2 3 2

输出：

4

1 3 1

总共n个零件，每种零件都有m种供应商的选择，共计\(m^n\)种可能性，并且更新最优解的算法时间复杂度为\(O(n)\)。

即使有减枝操作，但是算法时间复杂度仍为\(O(n*m^n)\)

为了保存当前解需要使用数组，算法空间复杂度为\(O(n)\)

最佳调度

问题描述

有n个任务由k个可并行工作的机器完成。完成任务i需要的时间为ti。找出完成这n个任务的最佳调度，使得完成全部任务的时间最少

第一行有2个正整数n和k，第二行有n个正整数，表示ti

样例输入

7 3
2 14 4 16 6 5 3

样例输出

17

算法描述

从n个作业中找出有最小完成时间和的作业调度，所以批处理作业调度问题的解空间是一棵组合选择树，可以用回溯算法解决。

设t=[0,1, ... , n-1]是所给的n个作业的完成时间，数组machineTime=[0,1,..,k-1]用于记录k个机器当前的工作时间情况，bestx记录相应的当前最佳作业调度完成时间。记i为递归深度，也就是当前处理的作业序号。

当i<=n-1时，若当前扩展结点位于排列树的第i-1层，此时算法搜索第i号作业可供安排的机器，以深度优先方式递归的对相应的子树进行搜索，对不满足上界约束的选择。当选择结束后，撤销此次选择，向 i-1 层回溯。

当i=n时，深度优先搜索结束，得到一个新的作业调度方案。此时算法适时更新当前最优值；

关键代码

	int n;//n个任务
    int k;//k个机器
    int[] t;//每个任务的耗时
    int[] machineTime; //每个机器的所花费时间
    int bestx;//最少时间

    public void backTrace(int i) {
        if (i == n) {
            int x = -1;
            //x为当前调度策略所需要的时间花费
            for (int j = 0; j < k; j++) {
                x = Math.max(x, machineTime[j]);
            }
            bestx = Math.min(x, bestx);
            return;
        }
        for (int j = 0; j < k; j++) {
            if (machineTime[j] + t[i] >= bestx) {
                continue;
            }
            machineTime[j] += t[i];
            backTrace(i + 1);
            machineTime[j] -= t[i];
        }
    }

结果分析

输入：

7 3
2 14 4 16 6 5 3

输出：

17

输入：

10 7
12 13 13 10 5 1 4 5 6 7

输出：

13

总共n个作业，每个作业都有k个机器可供选择，共计\(k^n\)种可能性，并且需要用\(O(k)\)的时间计算出每次调度安排的所需时间。

即使有减枝操作，但是算法时间复杂度仍为\(O(k*k^n)\)

为了保存每个机器所花费的时间，需要使用数组，算法空间复杂度为\(O(k)\)