104 lines
2.0 KiB
Plaintext
104 lines
2.0 KiB
Plaintext
supply[] = [ 50 60 50 50 ]
|
|
demand[] = [ 30 20 70 30 60 ]
|
|
costs[][] = [ [ 16 16 13 22 17 ] [ 14 14 13 19 15 ] [ 19 19 20 23 50 ] [ 50 12 50 15 11 ] ]
|
|
#
|
|
nrows = len supply[]
|
|
ncols = len demand[]
|
|
#
|
|
len row_done[] nrows
|
|
len col_done[] ncols
|
|
#
|
|
func[] diff j le is_row .
|
|
min1 = 1 / 0
|
|
for i = 1 to le
|
|
if is_row = 1
|
|
done = col_done[i]
|
|
else
|
|
done = row_done[i]
|
|
.
|
|
if done = 0
|
|
if is_row = 1
|
|
c = costs[j][i]
|
|
else
|
|
c = costs[i][j]
|
|
.
|
|
if c < min1
|
|
min2 = min1
|
|
min1 = c
|
|
minp = i
|
|
elif c < min2
|
|
min2 = c
|
|
.
|
|
.
|
|
.
|
|
return [ min2 - min1 min1 minp ]
|
|
.
|
|
func[] max_penalty len1 len2 is_row .
|
|
md = -1 / 0
|
|
for i = 1 to len1
|
|
if is_row = 1
|
|
done = row_done[i]
|
|
else
|
|
done = col_done[i]
|
|
.
|
|
if done = 0
|
|
res[] = diff i len2 is_row
|
|
if res[1] > md
|
|
md = res[1]
|
|
pm = i
|
|
mc = res[2]
|
|
pc = res[3]
|
|
.
|
|
.
|
|
.
|
|
if is_row = 1
|
|
return [ pm pc mc md ]
|
|
else
|
|
return [ pc pm mc md ]
|
|
.
|
|
.
|
|
func[] nextcell .
|
|
res1[] = max_penalty nrows ncols 1
|
|
res2[] = max_penalty ncols nrows 0
|
|
if res1[4] = res2[4]
|
|
if res1[3] < res2[3]
|
|
return res1[]
|
|
else
|
|
return res2[]
|
|
.
|
|
else
|
|
if res1[4] > res2[4]
|
|
return res2[]
|
|
else
|
|
return res1[]
|
|
.
|
|
.
|
|
.
|
|
proc main .
|
|
for v in supply[]
|
|
supplyleft += v
|
|
results[][] &= [ ]
|
|
len results[$][] ncols
|
|
.
|
|
while supplyleft > 0
|
|
cell[] = nextcell
|
|
r = cell[1]
|
|
c = cell[2]
|
|
q = lower demand[c] supply[r]
|
|
demand[c] -= q
|
|
if demand[c] = 0
|
|
col_done[c] = 1
|
|
.
|
|
supply[r] -= q
|
|
if supply[r] = 0
|
|
row_done[r] = 1
|
|
.
|
|
results[r][c] = q
|
|
supplyleft -= q
|
|
totalcost += q * costs[r][c]
|
|
.
|
|
print results[][]
|
|
print "Total cost: " & totalcost
|
|
.
|
|
main
|