⍝ 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

⍝∇ assign

Back to: code

Back to: Workspaces