-
Notifications
You must be signed in to change notification settings - Fork 1
/
Optimal Assignments
84 lines (62 loc) · 2.62 KB
/
Optimal Assignments
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
//-------------- Question----------------------
Have the function OptimalAssignments(strArr) read strArr which will represent an NxN matrix and it will be in the following format: ["(n,n,n...)","(...)",...]
where the n's represent integers. This matrix represents a machine at row i performing task at column j. The cost for this is matrix[i][j]. Your program should
determine what machine should perform what task so as to minimize the whole cost and it should return the pairings of machines to tasks in the following
format: (i-j)(...)... Only one machine can perform one task. For example: if strArr is ["(5,4,2)","(12,4,3)","(3,4,13)"] then your program should
return (1-3)(2-2)(3-1) because assigning the machines to these tasks gives the least cost. The matrix will range from 2x2 to 6x6, there will be no negative costs
in the matrix, and there will always be a unique answer.
//---------------------------------------------------
import java.util.*;
import java.io.*;
class Main {
public static List<Integer[]> permutations = new ArrayList<>();
public static Integer[] minPermutationsArr = new Integer[0];
public static Integer minCost = Integer.MAX_VALUE;
public static String OptimalAssignments(String[] strArr) {
// code mkvslg
Integer[][] matrix = new Integer[strArr.length][strArr.length];
minPermutationsArr = new Integer[matrix.length];
for(int i=0;i<strArr.length;i++){
String[] splitted = strArr[i].substring(1,strArr[i].length()-1).split(",");
for(int j=0;j<splitted.length;j++){
matrix[i][j] = Integer.parseInt(splitted[j]);
}
}
List<Integer> list = new ArrayList<>();
for(int i=0;i<matrix.length;i++){
list.add(i);
}
permute(list,0);
for(Integer[] permutation : permutations){
int cost =0;
for(int i=0;i<permutation.length;i++){
cost+=matrix[i][permutation[i]];
}
if(cost < minCost){
minCost=cost;
minPermutationsArr = permutation;
}
}
String result = "";
for(int i=0;i<minPermutationsArr.length;i++){
result +="("+(i+1)+"-"+(minPermutationsArr[i]+1)+")";
}
return result;
}
static void permute(List<Integer> list, int k){
for(int i=k;i<list.size();i++){
Collections.swap(list,i,k);
permute(list,k+1);
Collections.swap(list,k,i);
}
if(k==list.size()-1){
Integer[] arr = list.toArray(new Integer[list.size()]);
permutations.add(arr);
}
}
public static void main (String[] args) {
// keep this function call here
Scanner s = new Scanner(System.in);
System.out.print(OptimalAssignments(s.nextLine()));
}
}