140 lines
2.9 KiB
Go
140 lines
2.9 KiB
Go
package main
|
|
|
|
import (
|
|
"fmt"
|
|
"math"
|
|
)
|
|
|
|
var supply = []int{50, 60, 50, 50}
|
|
var demand = []int{30, 20, 70, 30, 60}
|
|
|
|
var costs = make([][]int, 4)
|
|
|
|
var nRows = len(supply)
|
|
var nCols = len(demand)
|
|
|
|
var rowDone = make([]bool, nRows)
|
|
var colDone = make([]bool, nCols)
|
|
var results = make([][]int, nRows)
|
|
|
|
func init() {
|
|
costs[0] = []int{16, 16, 13, 22, 17}
|
|
costs[1] = []int{14, 14, 13, 19, 15}
|
|
costs[2] = []int{19, 19, 20, 23, 50}
|
|
costs[3] = []int{50, 12, 50, 15, 11}
|
|
|
|
for i := 0; i < len(results); i++ {
|
|
results[i] = make([]int, nCols)
|
|
}
|
|
}
|
|
|
|
func nextCell() []int {
|
|
res1 := maxPenalty(nRows, nCols, true)
|
|
res2 := maxPenalty(nCols, nRows, false)
|
|
switch {
|
|
case res1[3] == res2[3]:
|
|
if res1[2] < res2[2] {
|
|
return res1
|
|
} else {
|
|
return res2
|
|
}
|
|
case res1[3] > res2[3]:
|
|
return res2
|
|
default:
|
|
return res1
|
|
}
|
|
}
|
|
|
|
func diff(j, l int, isRow bool) []int {
|
|
min1 := math.MaxInt32
|
|
min2 := min1
|
|
minP := -1
|
|
for i := 0; i < l; i++ {
|
|
var done bool
|
|
if isRow {
|
|
done = colDone[i]
|
|
} else {
|
|
done = rowDone[i]
|
|
}
|
|
if done {
|
|
continue
|
|
}
|
|
var c int
|
|
if isRow {
|
|
c = costs[j][i]
|
|
} else {
|
|
c = costs[i][j]
|
|
}
|
|
if c < min1 {
|
|
min2, min1, minP = min1, c, i
|
|
} else if c < min2 {
|
|
min2 = c
|
|
}
|
|
}
|
|
return []int{min2 - min1, min1, minP}
|
|
}
|
|
|
|
func maxPenalty(len1, len2 int, isRow bool) []int {
|
|
md := math.MinInt32
|
|
pc, pm, mc := -1, -1, -1
|
|
for i := 0; i < len1; i++ {
|
|
var done bool
|
|
if isRow {
|
|
done = rowDone[i]
|
|
} else {
|
|
done = colDone[i]
|
|
}
|
|
if done {
|
|
continue
|
|
}
|
|
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
|
|
}
|
|
}
|
|
if isRow {
|
|
return []int{pm, pc, mc, md}
|
|
}
|
|
return []int{pc, pm, mc, md}
|
|
}
|
|
|
|
func main() {
|
|
supplyLeft := 0
|
|
for i := 0; i < len(supply); i++ {
|
|
supplyLeft += supply[i]
|
|
}
|
|
totalCost := 0
|
|
for supplyLeft > 0 {
|
|
cell := nextCell()
|
|
r, c := cell[0], cell[1]
|
|
q := demand[c]
|
|
if q > supply[r] {
|
|
q = supply[r]
|
|
}
|
|
demand[c] -= q
|
|
if demand[c] == 0 {
|
|
colDone[c] = true
|
|
}
|
|
supply[r] -= q
|
|
if supply[r] == 0 {
|
|
rowDone[r] = true
|
|
}
|
|
results[r][c] = q
|
|
supplyLeft -= q
|
|
totalCost += q * costs[r][c]
|
|
}
|
|
|
|
fmt.Println(" A B C D E")
|
|
for i, result := range results {
|
|
fmt.Printf("%c", 'W' + i)
|
|
for _, item := range result {
|
|
fmt.Printf(" %2d", item)
|
|
}
|
|
fmt.Println()
|
|
}
|
|
fmt.Println("\nTotal cost =", totalCost)
|
|
}
|