86 lines
2.0 KiB
Nim
86 lines
2.0 KiB
Nim
import math, sequtils, strutils
|
|
|
|
var
|
|
supply = [50, 60, 50, 50]
|
|
demand = [30, 20, 70, 30, 60]
|
|
|
|
let
|
|
costs = [[16, 16, 13, 22, 17],
|
|
[14, 14, 13, 19, 15],
|
|
[19, 19, 20, 23, 50],
|
|
[50, 12, 50, 15, 11]]
|
|
|
|
nRows = supply.len
|
|
nCols = demand.len
|
|
|
|
var
|
|
rowDone = newSeq[bool](nRows)
|
|
colDone = newSeq[bool](nCols)
|
|
results = newSeqWith(nRows, newSeq[int](nCols))
|
|
|
|
|
|
proc diff(j, len: int; isRow: bool): array[3, int] =
|
|
var min1, min2 = int.high
|
|
var minP = -1
|
|
for i in 0..<len:
|
|
let done = if isRow: colDone[i] else: rowDone[i]
|
|
if done: continue
|
|
let c = if isRow: costs[j][i] else: costs[i][j]
|
|
if c < min1:
|
|
min2 = min1
|
|
min1 = c
|
|
minP = i
|
|
elif c < min2:
|
|
min2 = c
|
|
result = [min2 - min1, min1, minP]
|
|
|
|
|
|
proc maxPenalty(len1, len2: int; isRow: bool): array[4, int] =
|
|
var md = int.low
|
|
var pc, pm, mc = -1
|
|
for i in 0..<len1:
|
|
let done = if isRow: rowDone[i] else: colDone[i]
|
|
if done: continue
|
|
let res = diff(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
|
|
result = if isRow: [pm, pc, mc, md] else: [pc, pm, mc, md]
|
|
|
|
|
|
proc nextCell(): array[4, int] =
|
|
let res1 = maxPenalty(nRows, nCols, true)
|
|
let res2 = maxPenalty(nCols, nRows, false)
|
|
if res1[3] == res2[3]:
|
|
return if res1[2] < res2[2]: res1 else: res2
|
|
result = if res1[3] > res2[3]: res2 else: res1
|
|
|
|
|
|
when isMainModule:
|
|
|
|
var supplyLeft = sum(supply)
|
|
var totalCost = 0
|
|
|
|
while supplyLeft > 0:
|
|
let cell = nextCell()
|
|
let r = cell[0]
|
|
let c = cell[1]
|
|
let q = min(demand[c], supply[r])
|
|
dec demand[c], q
|
|
if demand[c] == 0: colDone[c] = true
|
|
dec supply[r], q
|
|
if supply[r] == 0: rowDone[r] = true
|
|
results[r][c] = q
|
|
dec supplyLeft, q
|
|
inc totalCost, q * costs[r][c]
|
|
|
|
echo " A B C D E"
|
|
for i, result in results:
|
|
stdout.write chr(i + ord('W'))
|
|
for item in result:
|
|
stdout.write " ", ($item).align(2)
|
|
echo()
|
|
echo "\nTotal cost = ", totalCost
|