问题描述
对给定的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()
网友评论