91 lines
2.3 KiB
Text
91 lines
2.3 KiB
Text
import "./math" for Nums
|
|
import "./fmt" for Fmt
|
|
|
|
var supply = [50, 60, 50, 50]
|
|
var demand = [30, 20, 70, 30, 60]
|
|
|
|
var costs = [
|
|
[16, 16, 13, 22, 17],
|
|
[14, 14, 13, 19, 15],
|
|
[19, 19, 20, 23, 50],
|
|
[50, 12, 50, 15, 11]
|
|
]
|
|
|
|
var nRows = supply.count
|
|
var nCols = demand.count
|
|
|
|
var rowDone = List.filled(nRows, false)
|
|
var colDone = List.filled(nCols, false)
|
|
var results = List.filled(nRows, null)
|
|
for (i in 0...nRows) results[i] = List.filled(nCols, 0)
|
|
|
|
var diff = Fn.new { |j, len, isRow|
|
|
var min1 = Num.maxSafeInteger
|
|
var min2 = min1
|
|
var minP = -1
|
|
for (i in 0...len) {
|
|
var done = isRow ? colDone[i] : rowDone[i]
|
|
if (!done) {
|
|
var c = isRow ? costs[j][i] : costs[i][j]
|
|
if (c < min1) {
|
|
min2 = min1
|
|
min1 = c
|
|
minP = i
|
|
} else if (c < min2) min2 = c
|
|
}
|
|
}
|
|
return [min2 - min1, min1, minP]
|
|
}
|
|
|
|
var maxPenalty = Fn.new { |len1, len2, isRow|
|
|
var md = Num.minSafeInteger
|
|
var pc = -1
|
|
var pm = -1
|
|
var mc = -1
|
|
for (i in 0...len1) {
|
|
var done = isRow ? rowDone[i] : colDone[i]
|
|
if (!done) {
|
|
var res = diff.call(i, len2, isRow)
|
|
if (res[0] > md) {
|
|
md = res[0] // max diff
|
|
pm = i // pos of max diff
|
|
mc = res[1] // min cost
|
|
pc = res[2] // pos of min cost
|
|
}
|
|
}
|
|
}
|
|
return isRow ? [pm, pc, mc, md] : [pc, pm, mc, md]
|
|
}
|
|
|
|
var nextCell = Fn.new {
|
|
var res1 = maxPenalty.call(nRows, nCols, true)
|
|
var res2 = maxPenalty.call(nCols, nRows, false)
|
|
if (res1[3] == res2[3]) return (res1[2] < res2[2]) ? res1 : res2
|
|
return (res1[3] > res2[3]) ? res2 : res1
|
|
}
|
|
|
|
var supplyLeft = Nums.sum(supply)
|
|
var totalCost = 0
|
|
while (supplyLeft > 0) {
|
|
var cell = nextCell.call()
|
|
var r = cell[0]
|
|
var c = cell[1]
|
|
var q = demand[c].min(supply[r])
|
|
demand[c] = demand[c] - q
|
|
if (demand[c] == 0) colDone[c] = true
|
|
supply[r] = supply[r] - q
|
|
if (supply[r] == 0) rowDone[r] = true
|
|
results[r][c] = q
|
|
supplyLeft = supplyLeft - q
|
|
totalCost = totalCost + q*costs[r][c]
|
|
}
|
|
|
|
System.print(" A B C D E")
|
|
var i = 0
|
|
for (result in results) {
|
|
Fmt.write("$c", "W".bytes[0] + i)
|
|
for (item in result) Fmt.write(" $2d", item)
|
|
System.print()
|
|
i = i + 1
|
|
}
|
|
System.print("\nTotal Cost = %(totalCost)")
|