蛮力法/任务分配

任务分配问题是一个全排列问题，先求全排列，再求最小成本任务分配方式

package xcrj.kchalgorithm.bruteForce;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/** * 任务分配问题 * 有n（n≥1）个任务需要分配给n个人执行，一人执行一个任务 * 第i个人执行第j个任务的成本是c[i][j]（1≤i，j≤n）。求出总成本最小的分配方案。 * <p> * <p> * 任务分配给人是一个全排列问题，人固定住，任务分配具有相对顺序，所以是全排列问题 * <p> * 增量蛮力法 * 1 * 12 | 21 * 123 312 132 | 321 231 213 * <p> * 递归： * 递归出口：要增加的数i>最大数n * 递归体：每次给原有排列 根据索引j增加i 产生1个新排列 * <p> * 步骤： * 1. 全排列，每种任务分配方式 * 2. 遍历全排列结果，求最小成本任务分配方式 */
public class DutyDistribution {
    
    // 人员数量=任务数量=4
    private static int n = 4;
    private static int[][] rdCosts = {
    {
    9, 2, 7, 8}, {
    6, 4, 3, 7}, {
    5, 8, 1, 8}, {
    7, 6, 9, 4}};
    // 存放全排列，24是全排列总个数，4!
    static Set<List<Integer>> fullPerm = new HashSet<>(24);

    static {
    
        List<Integer> list = new ArrayList<>(1);
        fullPerm.add(list);
    }

    public static void insertI(int i) {
    
        Set<List<Integer>> fullPermTemp = new HashSet<>(6);
        // 将原来排列集合中所有的排列放入临时集合中
        for (List<Integer> list : fullPerm) {
    
            // ！复制原来的排列集合中的排列，按索引j增加i
            for (int j = 0; j < i; j++) {
    
                List<Integer> listTemp = new ArrayList<>(3);
                for (Integer v : list) {
    
                    listTemp.add(v);
                }
                listTemp.add(j, i);
                fullPermTemp.add(listTemp);
            }
        }
        // 清除原来的排列集合
        fullPerm.clear();
        // 复制临时排列集合的所有排列到原来的排列集合
        for (List<Integer> list : fullPermTemp) {
    
            List<Integer> l = new ArrayList<>(3);
            for (Integer v : list) {
    
                l.add(v);
            }
            fullPerm.add(l);
        }
        // 清除临时排列集合
        fullPermTemp.clear();
    }

    public static void fullPermutation2(int i, int n) {
    
        if (i > n) System.out.println("全排列：" + fullPerm);
        else {
    
            insertI(i);
            fullPermutation2(i + 1, n);
        }
    }

    /*任务分配*/
    public static void dutyDistribution() {
    
        fullPermutation2(1, 4);
        // 最小任务分配成本
        int minCost = Integer.MAX_VALUE;
        // 最小成本任务分配
        List<Integer> minCostDuties = null;
        // 遍历每个任务分配方式，即遍历全排列；第i中任务分配方式，List<Integer>索引代表人，值代表任务
        for (List<Integer> duties : fullPerm) {
    
            // 一次任务分配的总成本
            int sumCost = 0;
            // j代表人的编号
            for (int j = 0; j < duties.size(); j++) {
    
                // -1原因，因为全排列的任务编号从1开始
                sumCost += rdCosts[j][duties.get(j) - 1];
            }
            // 比较成本
            if (sumCost < minCost) {
    
                minCost = sumCost;
                minCostDuties = duties;
            }
        }
        // 输出最小成本任务分配方式
        System.out.println(minCostDuties);
        // 输出任务分配最小成本
        System.out.println(minCost);
    }

    public static void main(String[] args) {
    
        dutyDistribution();
    }
}