From 3aa81e83dab59130ec0db541df58a167ff15070a Mon Sep 17 00:00:00 2001 From: Toby Vincent Date: Sat, 23 Oct 2021 18:20:27 -0500 Subject: Struct_bugfix (#1) * initial work finding bug * moved solution output into struct * added output formatting * fixed issue with rolling average * moved comment above main --- src/Program/Program.cs | 72 +++++++++++++++++++---------------------- src/SubsetSum/SolveSubsetSum.cs | 26 +++++++-------- 2 files changed, 47 insertions(+), 51 deletions(-) diff --git a/src/Program/Program.cs b/src/Program/Program.cs index 5dff2fc..70af96f 100644 --- a/src/Program/Program.cs +++ b/src/Program/Program.cs @@ -18,12 +18,19 @@ namespace Program public string Type; public int Value; public TimeSpan Runtime; - public override string ToString() => $"{Value} @ {Runtime.ToString("mm\\:ss\\.ff")}"; public void AddAverage(Solution solution, int count) { - Runtime = (Runtime + solution.Runtime) / count; - Value = (Value + solution.Value) / count; + Runtime = (Runtime * (count - 1) + solution.Runtime) / count; + Value = (Value * (count - 1) + solution.Value) / count; } + public void Output(FileInfo outputFile = null) + { + if (outputFile != null) + File.AppendAllText(outputFile.FullName, this.ToString() + "\n"); + Console.WriteLine($"{this.Type} Solution: {this.ToString()}"); + } + public override string ToString() + => $"{Value} @ {Runtime.TotalMilliseconds}"; } public struct Algorithm @@ -35,7 +42,7 @@ namespace Program class Program { static readonly Algorithm Dynamic = new Algorithm { Type = "Optimal", Func = SolveSubsetSum.Dynamic }; - static readonly Algorithm Greedy = new Algorithm { Type = "Approximate", Func = SolveSubsetSum.Greedy }; + static readonly Algorithm Greedy = new Algorithm { Type = "Approx.", Func = SolveSubsetSum.Greedy }; static Problem Defaults = new Problem { NumItems = 100, @@ -44,30 +51,31 @@ namespace Program Capacity = 1000, }; + /* + run 10 times + keep track of high, low, and average values + keep track of the runtime of each algorithm + random number generator + generate 100 possible items + items should have random weights between 1 - 600 + use dynamic algorithm to compute the optimal solution + + use greedy algorithm to compute approximate solution + */ static void Main(string[] args) { + Problem parameters = Defaults; FileInfo dynamicFile = new("dynamic.log"); FileInfo greedyFile = new("greedy.log"); - Problem parameters = Defaults; Solution averageDynamic = default(Solution); Solution averageGreedy = default(Solution); averageDynamic.Type = $"Average {Dynamic.Type}"; averageGreedy.Type = $"Average {Greedy.Type}"; - /* - run 10 times - keep track of high, low, and average values - keep track of the runtime of each algorithm - random number generator - generate 100 possible items - items should have random weights between 1 - 600 - - use dynamic algorithm to compute the optimal solution - - use greedy algorithm to compute approximate solution - */ + File.WriteAllText(dynamicFile.FullName, "[Score @ Runtime]\n"); + File.WriteAllText(greedyFile.FullName, "[Score @ Runtime]\n"); for (int i = 0; i < 10; i++) { @@ -78,14 +86,14 @@ namespace Program averageDynamic.AddAverage(dynamic, i + 1); averageGreedy.AddAverage(greedy, i + 1); - OutputSolution(dynamic, dynamicFile); - OutputSolution(greedy, greedyFile); - + dynamic.Output(dynamicFile); + greedy.Output(greedyFile); } - OutputSolution(averageDynamic, dynamicFile); - OutputSolution(averageGreedy, greedyFile); - + File.AppendAllText(dynamicFile.FullName, "[Average]\n"); + File.AppendAllText(greedyFile.FullName, "[Average]\n"); + averageDynamic.Output(dynamicFile); + averageGreedy.Output(greedyFile); } static int[] GenerateItems(Problem problem) @@ -101,22 +109,10 @@ namespace Program static Solution GenerateSolution(Algorithm algorithm, int[] items, int capacity) { - Stopwatch stopWatch = new Stopwatch(); - stopWatch.Restart(); - + Stopwatch runtime = Stopwatch.StartNew(); var solution = algorithm.Func(items, capacity); - TimeSpan runtime = stopWatch.Elapsed; - - stopWatch.Stop(); - return new Solution { Type = algorithm.Type, Value = solution, Runtime = runtime }; - } - - static void OutputSolution(Solution solution, FileInfo outputFile = null) - { - Console.WriteLine($"{solution.Type} Solution: {solution}"); - - if (outputFile != null) - File.WriteAllText(outputFile.FullName, solution.ToString()); + runtime.Stop(); + return new Solution { Type = algorithm.Type, Value = solution, Runtime = runtime.Elapsed }; } } } diff --git a/src/SubsetSum/SolveSubsetSum.cs b/src/SubsetSum/SolveSubsetSum.cs index 5541bf5..55de144 100644 --- a/src/SubsetSum/SolveSubsetSum.cs +++ b/src/SubsetSum/SolveSubsetSum.cs @@ -26,20 +26,20 @@ namespace SubsetSum //initialize "no items" row to all be weight 0 for (int i = 0; i < maxWeight; i++) - matrix[0,i] = 0; + matrix[0, i] = 0; - for(int i = 1; i < n; i++) + for (int i = 1; i < n; i++) { - for(int w = 1; w < maxWeight; w++) - { - if(items[i] > w) - matrix[i,w] = matrix[i-1,w]; - else - matrix[i,w] = Math.Max( matrix[i-1,w], (items[i] + matrix[i-1, w-items[i]]) ); - } + for (int w = 1; w < maxWeight; w++) + { + if (items[i] > w) + matrix[i, w] = matrix[i - 1, w]; + else + matrix[i, w] = Math.Max(matrix[i - 1, w], (items[i] + matrix[i - 1, w - items[i]])); + } } - return matrix[n,maxWeight]; + return matrix[n - 1, maxWeight - 1]; } /* @@ -53,10 +53,10 @@ namespace SubsetSum int weightAdded = 0; int i = 0; - Array.Sort(items, (a,b) => b.CompareTo(a)); + Array.Sort(items, (a, b) => b.CompareTo(a)); - while(i < items.Length && weightAdded + items[i] <= maxWeight) - weightAdded += items[i++]; + while (i < items.Length && weightAdded + items[i] <= maxWeight) + weightAdded += items[i++]; return weightAdded; } -- cgit v1.2.3-70-g09d2