Vogel's approximation method: Difference between revisions
Content added Content deleted
m (→{{header|Sidef}}: minor code simplifications) |
|||
Line 930: | Line 930: | ||
Total cost: 3100</pre> |
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}}== |
=={{header|Python}}== |