Transportation problem: Difference between revisions
Rename Perl 6 -> Raku, alphabetize, minor clean-up
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
|||
Line 446:
РешениеТранспортнойЗадачи();
КонецПроцедуры</lang>
=={{header|C sharp|C#}}==
{{trans|Java}}
<lang csharp>using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
namespace TransportationProblem {
class Shipment {
public Shipment(double q, double cpu, int r, int c) {
Quantity = q;
CostPerUnit = cpu;
R = r;
C = c;
}
public double CostPerUnit { get; }
public double Quantity { get; set; }
public int R { get; }
public int C { get; }
}
class Program {
private static int[] demand;
private static int[] supply;
private static double[,] costs;
private static Shipment[,] matrix;
static void Init(string filename) {
string line;
using (StreamReader file = new StreamReader(filename)) {
line = file.ReadLine();
var numArr = line.Split();
int numSources = int.Parse(numArr[0]);
int numDestinations = int.Parse(numArr[1]);
List<int> src = new List<int>();
List<int> dst = new List<int>();
line = file.ReadLine();
numArr = line.Split();
for (int i = 0; i < numSources; i++) {
src.Add(int.Parse(numArr[i]));
}
line = file.ReadLine();
numArr = line.Split();
for (int i = 0; i < numDestinations; i++) {
dst.Add(int.Parse(numArr[i]));
}
// fix imbalance
int totalSrc = src.Sum();
int totalDst = dst.Sum();
if (totalSrc > totalDst) {
dst.Add(totalSrc - totalDst);
} else if (totalDst > totalSrc) {
src.Add(totalDst - totalSrc);
}
supply = src.ToArray();
demand = dst.ToArray();
costs = new double[supply.Length, demand.Length];
matrix = new Shipment[supply.Length, demand.Length];
for (int i = 0; i < numSources; i++) {
line = file.ReadLine();
numArr = line.Split();
for (int j = 0; j < numDestinations; j++) {
costs[i, j] = int.Parse(numArr[j]);
}
}
}
}
static void NorthWestCornerRule() {
for (int r = 0, northwest = 0; r < supply.Length; r++) {
for (int c = northwest; c < demand.Length; c++) {
int quantity = Math.Min(supply[r], demand[c]);
if (quantity > 0) {
matrix[r, c] = new Shipment(quantity, costs[r, c], r, c);
supply[r] -= quantity;
demand[c] -= quantity;
if (supply[r] == 0) {
northwest = c;
break;
}
}
}
}
}
static void SteppingStone() {
double maxReduction = 0;
Shipment[] move = null;
Shipment leaving = null;
FixDegenerateCase();
for (int r = 0; r < supply.Length; r++) {
for (int c = 0; c < demand.Length; c++) {
if (matrix[r, c] != null) {
continue;
}
Shipment trial = new Shipment(0, costs[r, c], r, c);
Shipment[] path = GetClosedPath(trial);
double reduction = 0;
double lowestQuantity = int.MaxValue;
Shipment leavingCandidate = null;
bool plus = true;
foreach (var s in path) {
if (plus) {
reduction += s.CostPerUnit;
} else {
reduction -= s.CostPerUnit;
if (s.Quantity < lowestQuantity) {
leavingCandidate = s;
lowestQuantity = s.Quantity;
}
}
plus = !plus;
}
if (reduction < maxReduction) {
move = path;
leaving = leavingCandidate;
maxReduction = reduction;
}
}
}
if (move != null) {
double q = leaving.Quantity;
bool plus = true;
foreach (var s in move) {
s.Quantity += plus ? q : -q;
matrix[s.R, s.C] = s.Quantity == 0 ? null : s;
plus = !plus;
}
SteppingStone();
}
}
static List<Shipment> MatrixToList() {
List<Shipment> newList = new List<Shipment>();
foreach (var item in matrix) {
if (null != item) {
newList.Add(item);
}
}
return newList;
}
static Shipment[] GetClosedPath(Shipment s) {
List<Shipment> path = MatrixToList();
path.Add(s);
// remove (and keep removing) elements that do not have a
// vertical AND horizontal neighbor
int before;
do {
before = path.Count;
path.RemoveAll(ship => {
var nbrs = GetNeighbors(ship, path);
return nbrs[0] == null || nbrs[1] == null;
});
} while (before != path.Count);
// place the remaining elements in the correct plus-minus order
Shipment[] stones = path.ToArray();
Shipment prev = s;
for (int i = 0; i < stones.Length; i++) {
stones[i] = prev;
prev = GetNeighbors(prev, path)[i % 2];
}
return stones;
}
static Shipment[] GetNeighbors(Shipment s, List<Shipment> lst) {
Shipment[] nbrs = new Shipment[2];
foreach (var o in lst) {
if (o != s) {
if (o.R == s.R && nbrs[0] == null) {
nbrs[0] = o;
} else if (o.C == s.C && nbrs[1] == null) {
nbrs[1] = o;
}
if (nbrs[0] != null && nbrs[1] != null) {
break;
}
}
}
return nbrs;
}
static void FixDegenerateCase() {
const double eps = double.Epsilon;
if (supply.Length + demand.Length - 1 != MatrixToList().Count) {
for (int r = 0; r < supply.Length; r++) {
for (int c = 0; c < demand.Length; c++) {
if (matrix[r, c] == null) {
Shipment dummy = new Shipment(eps, costs[r, c], r, c);
if (GetClosedPath(dummy).Length == 0) {
matrix[r, c] = dummy;
return;
}
}
}
}
}
}
static void PrintResult(string filename) {
Console.WriteLine("Optimal solution {0}\n", filename);
double totalCosts = 0;
for (int r = 0; r < supply.Length; r++) {
for (int c = 0; c < demand.Length; c++) {
Shipment s = matrix[r, c];
if (s != null && s.R == r && s.C == c) {
Console.Write(" {0,3} ", s.Quantity);
totalCosts += (s.Quantity * s.CostPerUnit);
} else {
Console.Write(" - ");
}
}
Console.WriteLine();
}
Console.WriteLine("\nTotal costs: {0}\n", totalCosts);
}
static void Main() {
foreach (var filename in new string[] { "input1.txt", "input2.txt", "input3.txt" }) {
Init(filename);
NorthWestCornerRule();
SteppingStone();
PrintResult(filename);
}
}
}
}</lang>
{{out}}
<pre>Optimal solution input1.txt
20 - 5
- 30 5
Total costs: 180
Optimal solution input2.txt
- - - 12
20 - 10 10
- 30 - 3
Total costs: 130
Optimal solution input3.txt
- - - 14
- 9 - 1
10 - 5 -
- 5 7 -
- 1 - -
Total costs: 1000</pre>
=={{header|C++}}==
Line 797 ⟶ 1,072:
10 30 20 20
30 40 35 45
Optimal solution input3.txt
Line 3,216:
l1: d:=ReadKey;
END.</lang>
=={{header|Phix}}==
Line 3,857 ⟶ 3,793:
3 tests passed
</pre>
=={{header|Raku}}==
(formerly Perl 6)
{{works with|Rakudo|2019.03.1}}
Using [[Vogel's_approximation_method#Perl6|Vogel's approximation method]]:
<lang perl6>my %costs = :S1{:3C1, :5C2, :7C3}, :S2{:3C1, :2C2, :5C3};
my %demand = :20C1, :30C2, :10C3;
my %supply = :25S1, :35S2;
my @cols = %demand.keys.sort;
my %res;
my %g = (|%supply.keys.map: -> $x { $x => [%costs{$x}.sort(*.value)».key]}),
(|%demand.keys.map: -> $x { $x => [%costs.keys.sort({%costs{$_}{$x}})]});
while (+%g) {
my @d = %demand.keys.map: -> $x
{[$x, my $z = %costs{%g{$x}[0]}{$x},%g{$x}[1] ?? %costs{%g{$x}[1]}{$x} - $z !! $z]}
my @s = %supply.keys.map: -> $x
{[$x, my $z = %costs{$x}{%g{$x}[0]},%g{$x}[1] ?? %costs{$x}{%g{$x}[1]} - $z !! $z]}
@d = |@d.grep({ (.[2] == max @d».[2]) }).&min: :by(*.[1]);
@s = |@s.grep({ (.[2] == max @s».[2]) }).&min: :by(*.[1]);
my ($t, $f) = @d[2] == @s[2] ?? (@s[1],@d[1]) !! (@d[2],@s[2]);
my ($d, $s) = $t > $f ?? (@d[0],%g{@d[0]}[0]) !! (%g{@s[0]}[0], @s[0]);
my $v = %supply{$s} min %demand{$d};
%res{$s}{$d} += $v;
%demand{$d} -= $v;
if (%demand{$d} == 0) {
%supply.grep( *.value != 0 )».key.map: -> $v
{ %g{$v}.splice((%g{$v}.first: * eq $d, :k),1) };
%g{$d}:delete;
%demand{$d}:delete;
}
%supply{$s} -= $v;
if (%supply{$s} == 0) {
%demand.grep( *.value != 0 )».key.map: -> $v
{ %g{$v}.splice((%g{$v}.first: * eq $s, :k),1) };
%g{$s}:delete;
%supply{$s}:delete;
}
}
say join "\t", flat '', @cols;
my $total;
for %costs.keys.sort -> $g {
print "$g\t";
for @cols -> $col {
print %res{$g}{$col} // '-', "\t";
$total += (%res{$g}{$col} // 0) * %costs{$g}{$col};
}
print "\n";
}
say "\nTotal cost: $total";</lang>
{{out}}
<pre> C1 C2 C3
S1 20 - 5
S2 - 30 5 </pre>
=={{header|SAS}}==
| |||