69 lines
2.0 KiB
Plaintext
69 lines
2.0 KiB
Plaintext
sequence 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}}
|
|
|
|
sequence row_done = repeat(false,length(supply)),
|
|
col_done = repeat(false,length(demand))
|
|
|
|
function diff(integer j, leng, bool is_row)
|
|
integer min1 = #3FFFFFFF, min2 = min1, min_p = -1
|
|
for i=1 to leng do
|
|
if not iff(is_row?col_done:row_done)[i] then
|
|
integer c = iff(is_row?costs[j,i]:costs[i,j])
|
|
if c<min1 then
|
|
min2 = min1
|
|
min1 = c
|
|
min_p = i
|
|
elsif c<min2 then
|
|
min2 = c
|
|
end if
|
|
end if
|
|
end for
|
|
return {min2-min1,min1,min_p,j}
|
|
end function
|
|
|
|
function max_penalty(integer len1, len2, bool is_row)
|
|
integer pc = -1, pm = -1, mc = -1, md = -#3FFFFFFF
|
|
for i=1 to len1 do
|
|
if not iff(is_row?row_done:col_done)[i] then
|
|
sequence res2 = diff(i, len2, is_row)
|
|
if res2[1]>md then
|
|
{md,mc,pc,pm} = res2
|
|
end if
|
|
end if
|
|
end for
|
|
return {md,mc}&iff(is_row?{pm,pc}:{pc,pm})
|
|
end function
|
|
|
|
integer supply_left = sum(supply),
|
|
total_cost = 0
|
|
|
|
sequence results = repeat(repeat(0,length(demand)),length(supply))
|
|
|
|
while supply_left>0 do
|
|
sequence cell = min(max_penalty(length(supply), length(demand), true),
|
|
max_penalty(length(demand), length(supply), false))
|
|
integer {{},{},r,c} = cell,
|
|
q = min(demand[c], supply[r])
|
|
demand[c] -= q
|
|
col_done[c] = (demand[c]==0)
|
|
supply[r] -= q
|
|
row_done[r] = (supply[r]==0)
|
|
results[r, c] = q
|
|
supply_left -= q
|
|
total_cost += q * costs[r, c]
|
|
end while
|
|
|
|
printf(1," A B C D E\n")
|
|
for i=1 to length(supply) do
|
|
printf(1,"%c ",'Z'-length(supply)+i)
|
|
for j=1 to length(demand) do
|
|
printf(1,"%4d",results[i,j])
|
|
end for
|
|
printf(1,"\n")
|
|
end for
|
|
printf(1,"\nTotal cost = %d\n", total_cost)
|