Vogel's approximation method: Difference between revisions
→{{header|Phix}}
m (→{{header|Sidef}}: minor code simplifications) |
|||
Line 930:
Total cost: 3100</pre>
=={{header|Phix}}==
{{trans|YaBasic}}
{{trans|Go}}
<lang Phix>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)</lang>
{{out}}
<pre>
A B C D E
W 0 0 50 0 0
X 30 0 20 0 10
Y 0 20 0 30 0
Z 0 0 0 0 50
Total cost = 3100
</pre>
Using the sample from Ruby:
<lang Phix>sequence supply = {461, 277, 356, 488, 393},
demand = {278, 60, 461, 116, 1060},
costs = {{46, 74, 9, 28, 99},
{12, 75, 6, 36, 48},
{35, 199, 4, 5, 71},
{61, 81, 44, 88, 9},
{85, 60, 14, 25, 79}}</lang>
{{Out}}
<pre>
A B C D E
V 0 0 461 0 0
W 277 0 0 0 0
X 1 0 0 0 355
Y 0 0 0 0 488
Z 0 60 0 116 217
Total cost = 60748
</pre>
=={{header|Python}}==
| |||