Assign N tasks to N persons to minimize total time
There are N persons and N jobs. Given an array arr[] of size N*N where (arr[0], arr[1], . . ., arr[N-1]) denotes the time taken by the first person to perform (1st, 2nd, . . ., Nth) job respectively and similarly from arr[N] to arr[2*N -1] for the second and so on for other persons. The task is to assign each task to only one person and only one task to each person such that the total time taken by all the persons to finish all the jobs is minimum.
Examples:
Input: N = 2, Arr[] = {3, 5, 10, 1}
Output: 4
Explanation: The first person takes times 3 and 5 for jobs 1 and 2 respectively. The second person takes times 10 and 1 for jobs 1 and 2 respectively. We can see that the optimal assignment will be to give job 1 to person 1 and job 2 to person 2 for a total for 3 + 1 = 4.Input: N = 3, Arr[] = {2, 1, 2, 9, 8, 1, 1, 1, 1}
Output: 3
Explanation: The optimal arrangement would be to assign job 1 to person 3, job 2 to person 1 and job 3 to person 2.
Naive Approach: The basic way to solve the problem is as follows:
The problem can be solved by checking all the possible combinations formed and check the minimum time taken to complete the N jobs.
Follow the steps to solve this problem:
- By using the next permutation we can generate all possible permutations of the array of the workers who will get the task to do.
- After getting each permutation we will iterate through the N jobs and calculate the time taken to complete the task.
- After calculating all the time taken we will output the minimum time taken to complete the N jobs from all the permutations.
Below is the implementation of the above approach.
// C++ code to implement the approach:
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum total time
int assignmentProblem(int Arr[], int n)
{
vector<vector<int> > cost(n, vector<int>(n));
int ind = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cost[i][j] = Arr[ind];
ind++;
}
}
vector<int> permutation(n);
for (int i = 0; i < n; i++) {
permutation[i] = i;
}
int answer = 1e9;
do {
int temp_answer = 0;
for (int i = 0; i < n; i++) {
temp_answer += (cost[permutation[i]][i]);
}
answer = min(answer, temp_answer);
} while (next_permutation(permutation.begin(),
permutation.end()));
return answer;
}
// Driver Code
int main()
{
int arr[] = { 3, 5, 10, 1 };
int N = sqrt(sizeof(arr) / sizeof(arr[0]));
// Function Call
cout << assignmentProblem(arr, N) << endl;
return 0;
}
// Java code to implement the approach:
import java.util.*;
public class Main {
// Driver Code
public static void main(String[] args)
{
int arr[] = { 3, 5, 10, 1 };
int N = (int)Math.sqrt(arr.length);
// Function Call
System.out.println(assignmentProblem(arr, N));
}
// Function to find the minimum total time
public static int assignmentProblem(int Arr[], int n)
{
int[][] cost = new int[n][n];
int ind = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cost[i][j] = Arr[ind];
ind++;
}
}
int[] permutation = new int[n];
for (int i = 0; i < n; i++) {
permutation[i] = i;
}
int answer = Integer.MAX_VALUE;
do {
int tempAnswer = 0;
for (int i = 0; i < n; i++) {
tempAnswer += cost[permutation[i]][i];
}
answer = Math.min(answer, tempAnswer);
} while (next_permutation(permutation));
return answer;
}
// Function to swap the data
// present in the left and right indices
public static int[] swap(int permutation[], int left,
int right)
{
// Swap the data
int temp = permutation[left];
permutation[left] = permutation[right];
permutation[right] = temp;
// Return the updated array
return permutation;
}
// Function to reverse the sub-array
// starting from left to the right
// both inclusive
public static int[] reverse(int permutation[], int left,
int right)
{
// Reverse the sub-array
while (left < right) {
int temp = permutation[left];
permutation[left++] = permutation[right];
permutation[right--] = temp;
}
// Return the updated array
return permutation;
}
// Function to find the next permutation
// of the given integer array
public static boolean next_permutation(int permutation[])
{
// If the given dataset is empty
// or contains only one element
// next_permutation is not possible
if (permutation.length <= 1)
return false;
int last = permutation.length - 2;
// find the longest non-increasing suffix
// and find the pivot
while (last >= 0) {
if (permutation[last] < permutation[last + 1]) {
break;
}
last--;
}
// If there is no increasing pair
// there is no higher order permutation
if (last < 0)
return false;
int nextGreater = permutation.length - 1;
// Find the rightmost successor to the pivot
for (int i = permutation.length - 1; i > last;
i--) {
if (permutation[i] > permutation[last]) {
nextGreater = i;
break;
}
}
// Swap the successor and the pivot
permutation = swap(permutation, nextGreater, last);
// Reverse the suffix
permutation = reverse(permutation, last + 1,
permutation.length - 1);
// Return true as the next_permutation is done
return true;
}
}
// This code is contributed by Tapesh(tapeshdua420)
# Python code to implement the above approach
def swap(list, pos1, pos2):
list[pos1], list[pos2] = list[pos2], list[pos1]
return list
# Function to find the next permutation
def next_permutation(arr):
n = len(arr)
i = 0
j = 0
# Find for the pivot element.
# A pivot is the first element from
# end of sequencewhich doesn't follow
# property of non-increasing suffix
for i in range(n-2, -1, -1):
if (arr[i] < arr[i + 1]):
break
# Check if pivot is not found
if (i < 0):
arr.reverse()
# if pivot is found
else:
# Find for the successor of pivot in suffix
for j in range(n-1, i, -1):
if (arr[j] > arr[i]):
break
# Swap the pivot and successor
swap(arr, i, j)
# Minimise the suffix part
# initializing range
strt, end = i+1, len(arr)
# Third arg. of split with -1 performs reverse
arr[strt:end] = arr[strt:end][::-1]
# Function to find the minimum total time
def assignmentProblem(Arr, n):
cost = [[0 for i in range(n)] for j in range(n)]
ind = 0
for i in range(n):
for j in range(n):
cost[i][j] = Arr[ind]
ind += 1
permutation = [i for i in range(n)]
answer = 1e9
while True:
temp_answer = 0
for i in range(n):
temp_answer += (cost[permutation[i]][i])
answer = min(answer, temp_answer)
if not next_permutation(permutation):
break
return answer
# Driver Code
if __name__ == '__main__':
arr = [3, 5, 10, 1]
N = int(len(arr) ** 0.5)
# Function Call
print(assignmentProblem(arr, N))
# This code is contributed by Tapesh(tapeshdua420)
// C# code to implement the approach:
using System;
using System.Collections.Generic;
class Program {
// Driver Code
static void Main(string[] args)
{
int[] arr = { 3, 5, 10, 1 };
int N = (int)Math.Sqrt(arr.Length);
// Function Call
Console.WriteLine(assignmentProblem(arr, N));
}
// Function to find the minimum total time
public static int assignmentProblem(int[] Arr, int n)
{
int[][] cost = new int[n][];
for (int i = 0; i < n; i++) {
cost[i] = new int[n];
}
int ind = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cost[i][j] = Arr[ind];
ind++;
}
}
int[] permutation = new int[n];
for (int i = 0; i < n; i++) {
permutation[i] = i;
}
int answer = Int32.MaxValue;
do {
int tempAnswer = 0;
for (int i = 0; i < n; i++) {
tempAnswer += cost[permutation[i]][i];
}
answer = Math.Min(answer, tempAnswer);
} while (next_permutation(permutation));
return answer;
}
// Function to swap the data
// present in the left and right indices
public static int[] swap(int[] permutation, int left,
int right)
{
// Swap the data
int temp = permutation[left];
permutation[left] = permutation[right];
permutation[right] = temp;
// Return the updated array
return permutation;
}
// Function to reverse the sub-array
// starting from left to the right
// both inclusive
public static int[] reverse(int[] permutation, int left,
int right)
{
// Reverse the sub-array
while (left < right) {
int temp = permutation[left];
permutation[left++] = permutation[right];
permutation[right--] = temp;
}
// Return the updated array
return permutation;
}
// Function to find the next permutation
// of the given integer array
public static bool next_permutation(int[] permutation)
{
// If the given dataset is empty
// or contains only one element
// next_permutation is not possible
if (permutation.Length <= 1)
return false;
int last = permutation.Length - 2;
// find the longest non-increasing suffix
// and find the pivot
while (last >= 0) {
if (permutation[last] < permutation[last + 1]) {
break;
}
last--;
}
// If there is no increasing pair
// there is no higher order permutation
if (last < 0)
return false;
int nextGreater = permutation.Length - 1;
// Find the rightmost successor to the pivot
for (int i = permutation.Length - 1; i > last;
i--) {
if (permutation[i] > permutation[last]) {
nextGreater = i;
break;
}
}
// Swap the successor and the pivot
permutation = swap(permutation, nextGreater, last);
// Reverse the suffix
permutation = reverse(permutation, last + 1,
permutation.Length - 1);
// Return true as the next_permutation is done
return true;
}
}
// This code is contributed by Tapesh(tapeshdua420)
// Javascript code to implement the approach:
// Function to find the next permutation
function next_permutation(arr)
{
let n = arr.length, i, j;
// Find for the pivot element.
// A pivot is the first element from
// end of sequencewhich doesn't follow
// property of non-increasing suffix
for (i = n - 2; i >= 0; i--) {
if (arr[i] < arr[i + 1]) {
break;
}
}
// Check if pivot is not found
if (i < 0) {
arr.reverse();
}
// if pivot is found
else {
// Find for the successor of pivot in suffix
for (j = n - 1; j > i; j--) {
if (arr[j] > arr[i]) {
break;
}
}
// Swap the pivot and successor
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
// Minimise the suffix part
let arr1 = arr.slice(i+1, n);
arr1.reverse();
arr.splice(i+1, n, ...arr1);
}
}
// Function to find the minimum total time
function assignmentProblem(arr, n) {
var cost = [];
var ind = 0;
for (var i = 0; i < n; i++) {
cost[i] = [];
for (var j = 0; j < n; j++) {
cost[i][j] = arr[ind];
ind++;
}
}
var permutation = [];
for (var i = 0; i < n; i++) {
permutation[i] = i;
}
var answer = 1e9;
do {
var temp_answer = 0;
for (var i = 0; i < n; i++) {
temp_answer += (cost[permutation[i]][i]);
}
answer = Math.min(answer, temp_answer);
} while (next_permutation(permutation));
return answer;
}
// Driver Code
var arr = [3, 5, 10, 1];
var N = Math.sqrt(arr.length) | 0;
// Function Call
console.log(assignmentProblem(arr, N));
// This code is contributed by Tapesh(tapeshdua420)
Output
4
Time Complexity: O(N! * N) For calculating all the permutations it takes N! factorial time and in each permutation we will be calculating the time taken to complete the N jobs. So we need to traverse the N elements in each combination.
Auxiliary Space: O(N2) As we are given the time taken for each job done by each person. So there are N persons and N jobs so it takes the complexity of O(N2).
Efficient Approach: To solve the problem follow the below idea:
We will be using The Hungarian algorithm, aka Munkres assignment algorithm, utilizes the following theorem for polynomial runtime complexity and guaranteed optimal
Follow the steps to solve this problem:
- Create the cost matrix. The cost matrix is a square matrix where N persons for each job cost are given.
- If a number is added to or subtracted from all of the entries of any one row or column of a cost matrix, then an optimal assignment for the resulting cost matrix is also an optimal assignment for the original cost matrix.
- We reduce our original cost matrix to contain zeros, by using the above theorem. We try to assign tasks to agents such that each agent is doing only one task and the penalty incurred in each case is zero.
- For each row of the matrix, find the smallest element and subtract it from every element in its row.
- Do the same (as in step 2) for all columns.
- Cover all zeros in the matrix using the minimum number of horizontal and vertical lines.
- Test for Optimal: If the minimum number of covering lines is N, an optimal assignment is possible and we are finished.
Below is the implementation of the above approach.
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
int cost[31][31];
int n, max_match;
// Labels of X and Y parts
int lx[31], ly[31];
// xy[x] - vertex that is matched with x,
// yx[y] - vertex that is matched with y
int xy[31], yx[31];
bool S[31], T[31];
int slack[31];
int slackx[31];
int prev_ious[31];
void init_labels()
{
memset(lx, 0, sizeof(lx));
memset(ly, 0, sizeof(ly));
for (int x = 0; x < n; x++)
for (int y = 0; y < n; y++)
lx[x] = max(lx[x], cost[x][y]);
}
void update_labels()
{
int x, y;
// Init delta as infinity
int delta = 99999999;
// calculate delta using slack
for (y = 0; y < n; y++)
if (!T[y])
delta = min(delta, slack[y]);
// Update X labels
for (x = 0; x < n; x++)
if (S[x])
lx[x] -= delta;
// Update Y labels
for (y = 0; y < n; y++)
if (T[y])
ly[y] += delta;
// Update slack array
for (y = 0; y < n; y++)
if (!T[y])
slack[y] -= delta;
}
// x - current vertex, prev_iousx - vertex
// from X before x in the alternating path,
// so we add edges (prev_iousx,
// xy[x]), (xy[x], x)
void add_to_tree(int x, int prev_iousx)
{
// Add x to S
S[x] = true;
// We need this when augmenting
prev_ious[x] = prev_iousx;
// Update slacks, because we
// add new vertex to S
for (int y = 0; y < n; y++)
if (lx[x] + ly[y] - cost[x][y] < slack[y]) {
slack[y] = lx[x] + ly[y] - cost[x][y];
slackx[y] = x;
}
}
// Main function of the algorithm
void augment()
{
// Check whether matching is
// already perfect
if (max_match == n)
return;
// Just counters and root vertex
int x, y, root;
// q - queue for bfs, wr, rd - write
// and read pos in queue
int q[31], wr = 0, rd = 0;
// Initialize set S
memset(S, false, sizeof(S));
// Initialize set T
memset(T, false, sizeof(T));
// Initialize set prev_ious - for
// the alternating tree
memset(prev_ious, -1, sizeof(prev_ious));
// Finding root of the tree
for (x = 0; x < n; x++) {
if (xy[x] == -1) {
q[wr++] = root = x;
prev_ious[x] = -2;
S[x] = true;
break;
}
}
// Initializing slack array
for (y = 0; y < n; y++) {
slack[y] = lx[root] + ly[y] - cost[root][y];
slackx[y] = root;
}
// Second part of augment() function
while (true) {
// Building tree with bfs cycle
while (rd < wr) {
// Current vertex from X part
x = q[rd++];
for (y = 0; y < n;
// Iterate through all
// edges in equality graph
y++)
if (cost[x][y] == lx[x] + ly[y] && !T[y]) {
if (yx[y] == -1)
// An exposed vertex in Y
// found, so
// augmenting path exists!
break;
// Else just add y to T,
T[y] = true;
// Add vertex yx[y],
// which is matched
// with y, to the queue
q[wr++] = yx[y];
// Add edges (x, y) and
// (y, yx[y]) to the tree
add_to_tree(yx[y], x);
}
if (y < n)
break;
}
// Augmenting path found!
if (y < n)
break;
// Augmenting path not found, so
// improve labeling
update_labels();
wr = rd = 0;
for (y = 0; y < n; y++)
// In this cycle we add edges
// that were added to the
// equality graph as a result of
// improving the labeling, we add
// edge (slackx[y], y) to the
// tree if and only if !T[y] &&
// slack[y] == 0, also with this
// edge we add another one (y,
// yx[y]) or augment the matching,
// if y was exposed
if (!T[y] && slack[y] == 0) {
// Exposed vertex in Y found -
// augmenting path exists!
if (yx[y] == -1) {
x = slackx[y];
break;
}
else {
// Else just add y to T,
T[y] = true;
if (!S[yx[y]]) {
// Add vertex
// yx[y], which is
// matched with
// y, to the queue
q[wr++] = yx[y];
// Add edges
// (x, y) and
// (y, yx[y]) to the tree
add_to_tree(yx[y], slackx[y]);
}
}
}
if (y < n)
break;
}
// We found augmenting path!
if (y < n) {
// Increment matching
// in this cycle we inverse edges
// along augmenting path
max_match++;
for (int cx = x, cy = y, ty; cx != -2;
cx = prev_ious[cx], cy = ty) {
ty = xy[cx];
yx[cy] = cx;
xy[cx] = cy;
}
// Recall function, go to step 1 of
// the algorithm
augment();
}
}
int hungarian()
{
// Weight of the optimal matching
int ret = 0;
// Number of vertices in
// current matching
max_match = 0;
memset(xy, -1, sizeof(xy));
memset(yx, -1, sizeof(yx));
// Step 0
init_labels();
// Steps 1-3
augment();
// Forming answer there
for (int x = 0; x < n; x++)
ret += cost[x][xy[x]];
return ret;
}
// Function to find the minimum total time
int assignmentProblem(int Arr[], int N)
{
n = N;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cost[i][j] = -1 * Arr[i * n + j];
int ans = -1 * hungarian();
return ans;
}
// Driver Code
int main()
{
int arr[] = { 3, 5, 10, 1 };
int N = sqrt(sizeof(arr) / sizeof(arr[0]));
// Function Call
cout << assignmentProblem(arr, N);
return 0;
}
/*package whatever //do not write package name here */
import java.util.*;
class GFG {
static int cost[][] = new int[31][31];
static int n, max_match;
// Labels of X and Y parts
static int lx[] = new int[31];
static int ly[] = new int[31];
// xy[x] - vertex that is matched with x,
// yx[y] - vertex that is matched with y
static int xy[] = new int[31];
static int yx[] = new int[31];
static boolean S[] = new boolean[31];
static boolean T[] = new boolean[31];
static int slack[] = new int[31];
static int slackx[] = new int[31];
static int prev_ious[] = new int[31];
static void init_labels()
{
Arrays.fill(lx,0);
Arrays.fill(ly,0);
for (int x = 0; x < n; x++)
for (int y = 0; y < n; y++)
lx[x] = Math.max(lx[x], cost[x][y]);
}
static void update_labels()
{
int x, y;
// Init delta as infinity
int delta = 99999999;
// calculate delta using slack
for (y = 0; y < n; y++)
if (!T[y])
delta = Math.min(delta, slack[y]);
// Update X labels
for (x = 0; x < n; x++)
if (S[x])
lx[x] -= delta;
// Update Y labels
for (y = 0; y < n; y++)
if (T[y])
ly[y] += delta;
// Update slack array
for (y = 0; y < n; y++)
if (!T[y])
slack[y] -= delta;
}
// x - current vertex, prev_iousx - vertex
// from X before x in the alternating path,
// so we add edges (prev_iousx,
// xy[x]), (xy[x], x)
static void add_to_tree(int x, int prev_iousx)
{
// Add x to S
S[x] = true;
// We need this when augmenting
prev_ious[x] = prev_iousx;
// Update slacks, because we
// add new vertex to S
for (int y = 0; y < n; y++)
if (lx[x] + ly[y] - cost[x][y] < slack[y]) {
slack[y] = lx[x] + ly[y] - cost[x][y];
slackx[y] = x;
}
}
// Main function of the algorithm
static void augment()
{
// Check whether matching is
// already perfect
if (max_match == n)
return;
// Just counters and root vertex
int x=0, y=0, root=0;
// q - queue for bfs, wr, rd - write
// and read pos in queue
int q[] = new int[31];
int wr = 0, rd = 0;
// Initialize set S
// Initialize set prev_ious - for
// the alternating tree
Arrays.fill(prev_ious, -1);
// Finding root of the tree
for (x = 0; x < n; x++) {
if (xy[x] == -1) {
q[wr++] = root = x;
prev_ious[x] = -2;
S[x] = true;
break;
}
}
// Initializing slack array
for (y = 0; y < n; y++) {
slack[y] = lx[root] + ly[y] - cost[root][y];
slackx[y] = root;
}
// Second part of augment() function
while (true) {
// Building tree with bfs cycle
while (rd < wr) {
// Current vertex from X part
x = q[rd++];
for (y = 0; y < n;
// Iterate through all
// edges in equality graph
y++)
if (cost[x][y] == lx[x] + ly[y] && !T[y]) {
if (yx[y] == -1)
// An exposed vertex in Y
// found, so
// augmenting path exists!
break;
// Else just add y to T,
T[y] = true;
// Add vertex yx[y],
// which is matched
// with y, to the queue
q[wr++] = yx[y];
// Add edges (x, y) and
// (y, yx[y]) to the tree
add_to_tree(yx[y], x);
}
if (y < n)
break;
}
// Augmenting path found!
if (y < n)
break;
// Augmenting path not found, so
// improve labeling
update_labels();
wr = rd = 0;
for (y = 0; y < n; y++)
// In this cycle we add edges
// that were added to the
// equality graph as a result of
// improving the labeling, we add
// edge (slackx[y], y) to the
// tree if and only if !T[y] &&
// slack[y] == 0, also with this
// edge we add another one (y,
// yx[y]) or augment the matching,
// if y was exposed
if (!T[y] && slack[y] == 0) {
// Exposed vertex in Y found -
// augmenting path exists!
if (yx[y] == -1) {
x = slackx[y];
break;
}
else {
// Else just add y to T,
T[y] = true;
if (!S[yx[y]]) {
// Add vertex
// yx[y], which is
// matched with
// y, to the queue
q[wr++] = yx[y];
// Add edges
// (x, y) and
// (y, yx[y]) to the tree
add_to_tree(yx[y], slackx[y]);
}
}
}
if (y < n)
break;
}
// We found augmenting path!
if (y < n) {
// Increment matching
// in this cycle we inverse edges
// along augmenting path
max_match++;
for (int cx = x, cy = y, ty; cx != -2;
cx = prev_ious[cx], cy = ty) {
ty = xy[cx];
yx[cy] = cx;
xy[cx] = cy;
}
// Recall function, go to step 1 of
// the algorithm
augment();
}
}
static int hungarian()
{
// Weight of the optimal matching
int ret = 0;
// Number of vertices in
// current matching
max_match = 0;
Arrays.fill(xy, -1);
Arrays.fill(yx, -1);
// Step 0
init_labels();
// Steps 1-3
augment();
// Forming answer there
for (int x = 0; x < n; x++)
ret += cost[x][xy[x]];
return ret;
}
// Function to find the minimum total time
static int assignmentProblem(int Arr[], int N)
{
n = N;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cost[i][j] = -1 * Arr[i * n + j];
int ans = -1 * hungarian();
return ans;
}
public static void main (String[] args) {
int arr[] = { 3, 5, 10, 1 };
int N = (int)Math.sqrt(arr.length);
// Function Call
System.out.println(assignmentProblem(arr, N));
}
}
// This code is contributed by aadityaburujwale.
import numpy as np
n = 2
cost = np.array([[3, 99999999],
[99999999, 1]])
lx = np.zeros(n, dtype=int)
ly = np.zeros(n, dtype=int)
xy = np.full(n, -1, dtype=int)
yx = np.full(n, -1, dtype=int)
S = np.full(n, False)
T = np.full(n, False)
slack = np.full(n, 99999999, dtype=int)
slackx = np.zeros(n, dtype=int)
previous = np.full(n, 0, dtype=int)
max_match = 0
def init_labels():
global lx, ly
lx = np.max(cost, axis=1)
ly = np.zeros(n, dtype=int)
def update_labels():
global lx, ly, slack
delta = np.inf
for y in range(n):
if not T[y]:
delta = min(delta, slack[y])
for x in range(n):
if S[x]:
lx[x] -= delta
for y in range(n):
if T[y]:
ly[y] += delta
for y in range(n):
if not T[y]:
slack[y] -= delta
def add_to_tree(x, previousx):
global S, previous, slackx
S[x] = True
previous[x] = previousx
for y in range(n):
if lx[x] + ly[y] - cost[x][y] < slack[y]:
slack[y] = lx[x] + ly[y] - cost[x][y]
slackx[y] = x
def augment():
global max_match
if max_match == n:
return
q = np.zeros(n, dtype=int)
global S, T, previous, slack, slackx, xy, yx
wr = rd = 0
S.fill(False)
T.fill(False)
previous.fill(-1)
for x in range(n):
if xy[x] == -1:
q[wr] = x
wr += 1
root = x
previous[x] = -2
S[x] = True
break
slack.fill(99999999)
for y in range(n):
slack[y] = lx[root] + ly[y] - cost[root][y]
slackx[y] = root
while True:
while rd < wr:
x = q[rd]
rd += 1
for y in range(n):
if cost[x][y] == lx[x] + ly[y] and not T[y]:
if yx[y] == -1:
break
T[y] = True
q[wr] = yx[y]
wr += 1
add_to_tree(yx[y], x)
if y < n:
break
if y < n:
break
update_labels()
wr = rd = 0
for y in range(n):
if not T[y] and slack[y] == 0:
if yx[y] == -1:
x = slackx[y]
break
else:
T[y] = True
if not S[yx[y]]:
q[wr] = yx[y]
wr += 1
add_to_tree(yx[y], slackx[y])
if y < n:
break
if y < n:
max_match += 1
cx = x
cy = y
ty = 0
while cx != -2:
ty = xy[cx]
yx[cy] = cx
xy[cx] = cy
cx = previous[cx]
cy = ty
augment()
def hungarian():
global max_match
ret = 0
max_match = 0
xy.fill(-1)
yx.fill(-1)
init_labels()
augment()
for x in range(n):
ret += cost[x][xy[x]]
return ret
def assignmentProblem(Arr, N):
global cost, n
n = N
for i in range(n):
for j in range(n):
cost[i][j] = -1 * Arr[i * n + j]
ans = -1 * hungarian()
return ans
# Driver Code
arr = [3, 5, 10, 1]
N = int(np.sqrt(len(arr)))
print(assignmentProblem(arr, N)) # Output: 4
// C# code implementation for the above approach
using System;
using System.Collections;
public class GFG {
static int[, ] cost = new int[31, 31];
static int n, max_match;
// Labels of X and Y parts
static int[] lx = new int[31];
static int[] ly = new int[31];
// xy[x] - vertex that is matched with x,
// yx[y] - vertex that is matched with y
static int[] xy = new int[31];
static int[] yx = new int[31];
static bool[] S = new bool[31];
static bool[] T = new bool[31];
static int[] slack = new int[31];
static int[] slackx = new int[31];
static int[] prev_ious = new int[31];
static void init_labels()
{
Array.Fill(lx, 0);
Array.Fill(ly, 0);
for (int x = 0; x < n; x++)
for (int y = 0; y < n; y++)
lx[x] = Math.Max(lx[x], cost[x, y]);
}
static void update_labels()
{
int x, y;
// Init delta as infinity
int delta = 99999999;
// calculate delta using slack
for (y = 0; y < n; y++)
if (!T[y])
delta = Math.Min(delta, slack[y]);
// Update X labels
for (x = 0; x < n; x++)
if (S[x])
lx[x] -= delta;
// Update Y labels
for (y = 0; y < n; y++)
if (T[y])
ly[y] += delta;
// Update slack array
for (y = 0; y < n; y++)
if (!T[y])
slack[y] -= delta;
}
// x - current vertex, prev_iousx - vertex
// from X before x in the alternating path,
// so we add edges (prev_iousx,
// xy[x]), (xy[x], x)
static void add_to_tree(int x, int prev_iousx)
{
// Add x to S
S[x] = true;
// We need this when augmenting
prev_ious[x] = prev_iousx;
// Update slacks, because we
// add new vertex to S
for (int y = 0; y < n; y++)
if (lx[x] + ly[y] - cost[x, y] < slack[y]) {
slack[y] = lx[x] + ly[y] - cost[x, y];
slackx[y] = x;
}
}
// Main function of the algorithm
static void augment()
{
// Check whether matching is
// already perfect
if (max_match == n)
return;
// Just counters and root vertex
int x = 0, y = 0, root = 0;
// q - queue for bfs, wr, rd - write
// and read pos in queue
int[] q = new int[31];
int wr = 0, rd = 0;
// Initialize set S
// Initialize set prev_ious - for
// the alternating tree
Array.Fill(prev_ious, -1);
// Finding root of the tree
for (x = 0; x < n; x++) {
if (xy[x] == -1) {
q[wr++] = root = x;
prev_ious[x] = -2;
S[x] = true;
break;
}
}
// Initializing slack array
for (y = 0; y < n; y++) {
slack[y] = lx[root] + ly[y] - cost[root, y];
slackx[y] = root;
}
// Second part of augment() function
while (true) {
// Building tree with bfs cycle
while (rd < wr) {
// Current vertex from X part
x = q[rd++];
for (y = 0; y < n;
// Iterate through all
// edges in equality graph
y++)
if (cost[x, y] == lx[x] + ly[y]
&& !T[y]) {
if (yx[y] == -1)
// An exposed vertex in Y
// found, so
// augmenting path exists!
break;
// Else just add y to T,
T[y] = true;
// Add vertex yx[y],
// which is matched
// with y, to the queue
q[wr++] = yx[y];
// Add edges (x, y) and
// (y, yx[y]) to the tree
add_to_tree(yx[y], x);
}
if (y < n)
break;
}
// Augmenting path found!
if (y < n)
break;
// Augmenting path not found, so
// improve labeling
update_labels();
wr = rd = 0;
for (y = 0; y < n; y++)
// In this cycle we add edges
// that were added to the
// equality graph as a result of
// improving the labeling, we add
// edge (slackx[y], y) to the
// tree if and only if !T[y] &&
// slack[y] == 0, also with this
// edge we add another one (y,
// yx[y]) or augment the matching,
// if y was exposed
if (!T[y] && slack[y] == 0) {
// Exposed vertex in Y found -
// augmenting path exists!
if (yx[y] == -1) {
x = slackx[y];
break;
}
else {
// Else just add y to T,
T[y] = true;
if (!S[yx[y]]) {
// Add vertex
// yx[y], which is
// matched with
// y, to the queue
q[wr++] = yx[y];
// Add edges
// (x, y) and
// (y, yx[y]) to the tree
add_to_tree(yx[y], slackx[y]);
}
}
}
if (y < n)
break;
}
// We found augmenting path!
if (y < n) {
// Increment matching
// in this cycle we inverse edges
// along augmenting path
max_match++;
for (int cx = x, cy = y, ty; cx != -2;
cx = prev_ious[cx], cy = ty) {
ty = xy[cx];
yx[cy] = cx;
xy[cx] = cy;
}
// Recall function, go to step 1 of
// the algorithm
augment();
}
}
static int hungarian()
{
// Weight of the optimal matching
int ret = 0;
// Number of vertices in
// current matching
max_match = 0;
Array.Fill(xy, -1);
Array.Fill(yx, -1);
// Step 0
init_labels();
// Steps 1-3
augment();
// Forming answer there
for (int x = 0; x < n; x++)
ret += cost[x, xy[x]];
return ret;
}
// Function to find the minimum total time
static int assignmentProblem(int[] Arr, int N)
{
n = N;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cost[i, j] = -1 * Arr[i * n + j];
int ans = -1 * hungarian();
return ans;
}
static public void Main()
{
// Code
int[] arr = { 3, 5, 10, 1 };
int N = (int)Math.Sqrt(arr.Length);
// Function Call
Console.WriteLine(assignmentProblem(arr, N));
}
}
// This code is contributed by lokeshmvs21.
// Javascript code to implement the approach
let cost=new Array(31);
for(let i=0; i<31; i++)
cost[i]=new Array(31);
let n, max_match;
// Labels of X and Y parts
let lx=new Array(31), ly=new Array(31);
// xy[x] - vertex that is matched with x,
// yx[y] - vertex that is matched with y
let xy=new Array(31), yx=new Array(31);
let S=new Array(31), T=new Array(31);
let slack=new Array(31);
let slackx=new Array(31);
let prev_ious=new Array(31);
function memset(dp, x)
{
for(let i=0; i<dp.length; i++)
dp[i]=x;
}
function init_labels()
{
memset(lx, 0);
memset(ly, 0);
for (let x = 0; x < n; x++)
for (let y = 0; y < n; y++)
lx[x] = Math.max(lx[x], cost[x][y]);
}
function update_labels()
{
let x, y;
// Init delta as infinity
let delta = 99999999;
// calculate delta using slack
for (y = 0; y < n; y++)
if (!T[y])
delta = Math.min(delta, slack[y]);
// Update X labels
for (x = 0; x < n; x++)
if (S[x])
lx[x] -= delta;
// Update Y labels
for (y = 0; y < n; y++)
if (T[y])
ly[y] += delta;
// Update slack array
for (y = 0; y < n; y++)
if (!T[y])
slack[y] -= delta;
}
// x - current vertex, prev_iousx - vertex
// from X before x in the alternating path,
// so we add edges (prev_iousx,
// xy[x]), (xy[x], x)
function add_to_tree(x, prev_iousx)
{
// Add x to S
S[x] = true;
// We need this when augmenting
prev_ious[x] = prev_iousx;
// Update slacks, because we
// add new vertex to S
for (let y = 0; y < n; y++)
if (lx[x] + ly[y] - cost[x][y] < slack[y]) {
slack[y] = lx[x] + ly[y] - cost[x][y];
slackx[y] = x;
}
}
// Main function of the algorithm
function augment()
{
// Check whether matching is
// already perfect
if (max_match == n)
return;
// Just counters and root vertex
let x, y, root;
// q - queue for bfs, wr, rd - write
// and read pos in queue
let q=new Array(31);
let wr = 0, rd = 0;
// Initialize set S
memset(S, false);
// Initialize set T
memset(T, false);
// Initialize set prev_ious - for
// the alternating tree
memset(prev_ious, -1);
// Finding root of the tree
for (x = 0; x < n; x++) {
if (xy[x] == -1) {
q[wr++] = root = x;
prev_ious[x] = -2;
S[x] = true;
break;
}
}
// Initializing slack array
for (y = 0; y < n; y++) {
slack[y] = lx[root] + ly[y] - cost[root][y];
slackx[y] = root;
}
// Second part of augment() function
while (true) {
// Building tree with bfs cycle
while (rd < wr) {
// Current vertex from X part
x = q[rd++];
for (y = 0; y < n;
// Iterate through all
// edges in equality graph
y++)
if (cost[x][y] == lx[x] + ly[y] && !T[y]) {
if (yx[y] == -1)
// An exposed vertex in Y
// found, so
// augmenting path exists!
break;
// Else just add y to T,
T[y] = true;
// Add vertex yx[y],
// which is matched
// with y, to the queue
q[wr++] = yx[y];
// Add edges (x, y) and
// (y, yx[y]) to the tree
add_to_tree(yx[y], x);
}
if (y < n)
break;
}
// Augmenting path found!
if (y < n)
break;
// Augmenting path not found, so
// improve labeling
update_labels();
wr = rd = 0;
for (y = 0; y < n; y++)
// In this cycle we add edges
// that were added to the
// equality graph as a result of
// improving the labeling, we add
// edge (slackx[y], y) to the
// tree if and only if !T[y] &&
// slack[y] == 0, also with this
// edge we add another one (y,
// yx[y]) or augment the matching,
// if y was exposed
if (!T[y] && slack[y] == 0) {
// Exposed vertex in Y found -
// augmenting path exists!
if (yx[y] == -1) {
x = slackx[y];
break;
}
else {
// Else just add y to T,
T[y] = true;
if (!S[yx[y]]) {
// Add vertex
// yx[y], which is
// matched with
// y, to the queue
q[wr++] = yx[y];
// Add edges
// (x, y) and
// (y, yx[y]) to the tree
add_to_tree(yx[y], slackx[y]);
}
}
}
if (y < n)
break;
}
// We found augmenting path!
if (y < n) {
// Increment matching
// in this cycle we inverse edges
// along augmenting path
max_match++;
for (let cx = x, cy = y, ty; cx != -2;
cx = prev_ious[cx], cy = ty) {
ty = xy[cx];
yx[cy] = cx;
xy[cx] = cy;
}
// Recall function, go to step 1 of
// the algorithm
augment();
}
}
function hungarian()
{
// Weight of the optimal matching
let ret = 0;
// Number of vertices in
// current matching
max_match = 0;
memset(xy, -1);
memset(yx, -1);
// Step 0
init_labels();
// Steps 1-3
augment();
// Forming answer there
for (let x = 0; x < n; x++)
ret += cost[x][xy[x]];
return ret;
}
// Function to find the minimum total time
function assignmentProblem(Arr, N)
{
n = N;
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++)
cost[i][j] = -1 * Arr[i * n + j];
let ans = -1 * hungarian();
return ans;
}
// Driver Code
let arr = [3, 5, 10, 1 ];
let N = Math.sqrt(arr.length);
// Function Call
console.log(assignmentProblem(arr, N));
Output
4
Time Complexity: O(N2)
Auxiliary Space: O(N2)
Contact Us