-
Notifications
You must be signed in to change notification settings - Fork 0
/
Assignment Problem.cpp
116 lines (106 loc) · 2.54 KB
/
Assignment Problem.cpp
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <bits/stdc++.h>
using namespace std;
#define N 4
struct Node
{
Node* parent;
int pathCost;
int cost;
int workerID;
int jobID;
bool assigned[N];
};
Node* newNode(int x, int y, bool assigned[],
Node* parent)
{
Node* node = new Node;
for (int j = 0; j < N; j++)
node->assigned[j] = assigned[j];
node->assigned[y] = true;
node->parent = parent;
node->workerID = x;
node->jobID = y;
return node;
}
int calculateCost(int costMatrix[N][N], int x,
int y, bool assigned[])
{
int cost = 0;
bool available[N] = {true};
for (int i = x + 1; i < N; i++)
{
int min = INT_MAX, minIndex = -1;
for (int j = 0; j < N; j++)
{
if (!assigned[j] && available[j] &&
costMatrix[i][j] < min)
{
minIndex = j;
min = costMatrix[i][j];
}
}
cost += min;
available[minIndex] = false;
}
return cost;
}
struct comp
{
bool operator()(const Node* lhs,
const Node* rhs) const
{
return lhs->cost > rhs->cost;
}
};
void printAssignments(Node *min)
{
if(min->parent==NULL)
return;
printAssignments(min->parent);
cout << "Assign Worker " << char(min->workerID + 'A')
<< " to Job " << min->jobID << endl;
}
int findMinCost(int costMatrix[N][N])
{
priority_queue<Node*, std::vector<Node*>, comp> pq;
bool assigned[N] = {false};
Node* root = newNode(-1, -1, assigned, NULL);
root->pathCost = root->cost = 0;
root->workerID = -1;
pq.push(root);
while (!pq.empty())
{
Node* min = pq.top();
pq.pop();
int i = min->workerID + 1;
if (i == N)
{
printAssignments(min);
return min->cost;
}
for (int j = 0; j < N; j++)
{
if (!min->assigned[j])
{
Node* child = newNode(i, j, min->assigned, min);
child->pathCost = min->pathCost + costMatrix[i][j];
child->cost = child->pathCost +
calculateCost(costMatrix, i, j, child->assigned);
pq.push(child);
}
}
}
}
int main()
{
int costMatrix[N][N] =
{
{18, 26, 17, 11},
{13, 28, 14, 26},
{38, 19, 18, 10},
{19, 26, 24, 10}
};
cout << "\nOptimal Cost is "
<< findMinCost(costMatrix);
return 0;
}