-
Notifications
You must be signed in to change notification settings - Fork 1
/
assignment-ajax.php
75 lines (66 loc) · 1.69 KB
/
assignment-ajax.php
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
<?php
class TaskAssignment{
private $minAssign; // pessoas associadas as tarefas
private $minCost; // menor custo
// executa algoritmo
public function start($matrix)
{
$this->minCost = PHP_INT_MAX;
for($i=0; $i<count($matrix); $i++){
$this->minAssign[$i] = PHP_INT_MAX;
}
$assoc = array();
$this->branchAndBound($matrix, $assoc, 0);
return $this->minAssign;
}
// calculo as soluções utilizando branch and bound
public function branchAndBound($matrix, $assoc, $relCost)
{
if( (count($this->minAssign) == count($assoc)) && ($relCost < $this->minCost))
{
for($b=0; $b<count($this->minAssign); $b++){
$this->minAssign[$b] = $assoc[$b];
}
$this->minCost = $relCost;
}
else{
for($c = 0; $c < count($matrix); $c++)
{
if( ($this->verify($assoc, $c)) && ($relCost + $matrix[count($assoc)][$c] < $this->minCost))
{
$index = count($assoc);
array_push($assoc, $c);
$this->branchAndBound($matrix, $assoc, ($relCost+$matrix[$index][$c]));
unset($assoc[$index]);
$assoc = array_values($assoc);
}
}
}
}
// verifico se a pessoa já existe no array
public function verify($assoc, $col)
{
foreach($assoc as $a)
{
if($a == $col) return false;
}
return true;
}
public function getBestSolution(){
return $this->minCost;
}
public function getBestState()
{
return $this->minAssign;
}
}
echo "<br><br>";
$costs = $_POST['works'];
$obj = new TaskAssignment;
$obj->start($costs);
echo "A melhor solução para o problema é:<br>";
foreach($obj->getBestState() as $key => $item):
echo "Funcionário ".$key." fará a <b>Tarefa ".$item."</b><br>";
endforeach;
echo "O custo total será de: <b>".$obj->getBestSolution()."</b>";
?>