⍝ Hungarian method cost assignment:
⎕ml←0
costs←↑(72 99 88)(23 30 35)(51 59 84)
costs ⍝ example cost matrix.
72 99 88
23 30 35
51 59 84
assign costs ⍝ minimum cost assignment.
1 0 0
0 0 1
0 1 0
assign -costs ⍝ maximum benefit assignment.
0 1 0
1 0 0
0 0 1
+/+/ ×∘assign⍨ costs ⍝ total minimum cost.
166
+/+/ -×∘assign⍨ -costs ⍝ total maximum benefit.
206
costs←↑(7 38 23 27 11 3 34 34 47 20)(26 42 2 3 27 34 1 20 4 21)(35 30 47 43 27 5 33 21 36 46)(39 14 3 37 17 32 38 50 19 13)(50 37 38 33 4 32 45 14 22 39)(24 12 14 18 9 25 45 46 4 46)
costs
7 38 23 27 11 3 34 34 47 20
26 42 2 3 27 34 1 20 4 21
35 30 47 43 27 5 33 21 36 46
39 14 3 37 17 32 38 50 19 13
50 37 38 33 4 32 45 14 22 39
24 12 14 18 9 25 45 46 4 46
assign costs ⍝ minimum cost assignment.
1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0
{⍵×assign ⍵} costs ⍝ cost per assignment.
7 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 5 0 0 0 0
0 0 3 0 0 0 0 0 0 0
0 0 0 0 4 0 0 0 0 0
0 0 0 0 0 0 0 0 4 0
{+/+/⍵×assign ⍵} costs ⍝ total minimum cost.
24
assign -costs ⍝ maximum benefit assignment.
0 0 0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0
1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1
{-⍵×assign ⍵} -costs ⍝ cost per assignment.
0 0 0 0 0 0 0 0 47 0
0 42 0 0 0 0 0 0 0 0
0 0 47 0 0 0 0 0 0 0
0 0 0 0 0 0 0 50 0 0
50 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 46
{+/+/-⍵×assign ⍵} -costs ⍝ total maximum benefit.
282
costs←↑(14 1 21 2 36 47)(12 10 16 45 33 8)(35 20 20 25 8 30)(43 30 48 28 8 50)(21 8 29 13 25 24)(49 7 10 16 32 7)(33 32 41 13 24 20)(11 2 46 22 8 48)(21 7 45 5 9 4)(19 13 7 40 23 18)
costs
14 1 21 2 36 47
12 10 16 45 33 8
35 20 20 25 8 30
43 30 48 28 8 50
21 8 29 13 25 24
49 7 10 16 32 7
33 32 41 13 24 20
11 2 46 22 8 48
21 7 45 5 9 4
19 13 7 40 23 18
assign costs ⍝ minimum cost assignment.
0 1 0 0 0 0
1 0 0 0 0 0
0 0 0 0 1 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1
0 0 0 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 0 0
Back to: code
Back to: Workspaces
Trouble seeing APL font?