分配问题*

2019-11-22  本文已影响0人  asdfgjsrgdf

问题描述

       对给定的n个任务与n个人之间的成本矩阵完成成本最低的任务分配策略。

输入

       输入:第一行为用例个数,之后为每一个用例;用例的第一行为任务个数,即n;用例的第二行为使用逗号隔开的人员完成任务的成本;每一个成本描述包括人员序号、任务序号和成本,使用空格隔开。人员序号和任务序号都是从1到n的整数,序号出现的次序没有固定规则。

输出

       输出:每一个用例输出一行,从序号为1的人员开始,给出其分配的任务序号,使用空格隔开;使用逗号将多个解隔开。结果按照人员分配的任务序号大小排,第一个人员的任务序号大的放在前面,如果相同则看第二个人员的任务,以此类推。

示例输入

1
4
2 1 6,1 2 2,1 3 7,1 4 8,1 1 9,2 2 4,2 3 3,2 4 7,3 1 5,3 2 8,3 3 1,3 4 8,4 1 7,4 2 6,4 3 9,4 4 4

示例输出

2 1 3 4

思路(回溯)

       初始化:
1.任务分配数组:BestM={1,2,3,..... ,n}
2.最优方案总成本Bmin=99999
       在进行第t次递归中,依次交换工人t与工人i(i=t~n)的工作分配,若交换后的结果小于Bmin,则进入下一层递归,若递归层数t=n,则更新Bmin以及BestM,然后返回上一层。每当从t+1层递归中返回后,则按照回溯的思想取消t层递归中的交换,进入下一次循环(i++),循环结束后BestM中保存的分配即为最佳分配。

java代码

import java.util.Scanner;

public class Main{
    static int[] BestM;
    static int Bmin = 99999;

    static int sum(int k,int[][] inputs,int[] result){
        int temp=0;
        for(int i=1;i<=k;i++)
            temp+=inputs[i][result[i]];
        return temp;
    }

    static void backtrack(int t,int n, int[][] inputs, int[] result) {
        if (t == n) {
            int ans = sum(n,inputs,result);
            if (ans < Bmin) {
                Bmin = ans;
                for (int i = 1; i <= n; i++)
                    BestM[i] = result[i];
            }
        }
        else{
            for (int i=t;i<=n;i++) {
                int temp1 = result[t];
                result[t] = result[i];
                result[i] = temp1;
                if(sum(t,inputs,result)<Bmin)
                    backtrack(t+1,n,inputs,result);
                int temp2 = result[t];
                result[t] = result[i];
                result[i] = temp2;
            }
        }
    }
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int casesnum = sc.nextInt();
        while(casesnum>0){
            int n = sc.nextInt();
            int[][] inputs = new int[n+1][n+1];
            int[] result = new int[n+1];
            BestM = new int[n+1];
            sc.nextLine();
            String[] temp = sc.nextLine().split(",");
            for(int i=0;i<temp.length;i++){
                inputs[temp[i].charAt(0)-48][temp[i].charAt(2)-48] = temp[i].charAt(4)-48;
            }
            for (int i=1;i<=n;i++)
                result[i] = i;
            backtrack(1,n,inputs,result);
            for (int i=1;i<BestM.length;i++){
                System.out.print(BestM[i]);
                if(i<BestM.length-1)
                    System.out.print(" ");
                else
                    System.out.println();
            }
            Bmin = 99999;
            casesnum --;
        }
    }
}

python代码


def mysort(sortindex):
    keyset=""
    for i in range(sortindex):
        keyset+= "x["+str(i)+"],"
    keyset = keyset.rstrip(",")
    result.sort(key=lambda x:eval(keyset),reverse=True)
    
def myprint():
    for i in range(len(result)):
        for j in range(len(result[0])):
            if i == len(result)-1 and j == len(result[0])-1:
                print(result[i][j])
            elif i != len(result)-1 and j == len(result[0])-1:
                print(result[i][j],end=',')
            else:
                print(result[i][j] , end=' ')


def work( i , count , res_temp):
    global cost
    res_temp_copy = res_temp.copy()
    if i > n :
        if count == cost:
            if res_temp_copy not in result:
                result.append(res_temp_copy)
        if count < cost:
            result.clear()
            result.append(res_temp_copy)
            cost = count
    if count <= cost:
        for j in range(1,n+1):
            if x[j] == 0 :
                res_temp.append(j)
                x[j] = 1
                work(  i + 1 , count+costMatrix[i][j] , res_temp)
                res_temp.pop()
                x[j] = 0



if __name__=='__main__':
    numOfExamples = int(input())
    x = [ 0 for i in range(1000)]
    for c in range(numOfExamples):
        n = int(input())
        costMatrix = [[0 for j in range(n + 1)] for i in range(n + 1)]
        strarray = input().split(',')
        for j in range(0, len(strarray)):
            temp_array = []
            tempArray = strarray[j].split(' ')
            costMatrix[int(tempArray[0])][int(tempArray[1])] = int(tempArray[2])
        cost = 0
        res_temp = []
        result = []
        for i in range( 1 , len(costMatrix)):
            cost += costMatrix[i][i]
            res_temp.append(i)
        result.append(res_temp)
        work(1,0, [])
        mysort(len(result[0]))
        myprint()
上一篇 下一篇

猜你喜欢

热点阅读