1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
|
using System;
using System.Diagnostics;
using System.IO;
using SubsetSum;
namespace Program
{
public struct Problem
{
public int NumItems;
public int MinItemWeight;
public int MaxItemWeight;
public int Capacity;
}
public struct Solution
{
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;
}
}
public struct Algorithm
{
public string Type;
public Func<int[], int, int> Func;
}
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 Problem Defaults = new Problem
{
NumItems = 100,
MinItemWeight = 1,
MaxItemWeight = 600,
Capacity = 1000,
};
static void Main(string[] args)
{
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
*/
for (int i = 0; i < 10; i++)
{
var items = GenerateItems(parameters);
Solution dynamic = GenerateSolution(Dynamic, items, parameters.Capacity);
Solution greedy = GenerateSolution(Greedy, items, parameters.Capacity);
averageDynamic.AddAverage(dynamic, i + 1);
averageGreedy.AddAverage(greedy, i + 1);
OutputSolution(dynamic, dynamicFile);
OutputSolution(greedy, greedyFile);
}
OutputSolution(averageDynamic, dynamicFile);
OutputSolution(averageGreedy, greedyFile);
}
static int[] GenerateItems(Problem problem)
{
var random = new Random();
var items = new int[problem.NumItems];
for (int i = 0; i < items.Length; i++)
items[i] = random.Next(problem.MinItemWeight, problem.MaxItemWeight + 1);
return items;
}
static Solution GenerateSolution(Algorithm algorithm, int[] items, int capacity)
{
Stopwatch stopWatch = new Stopwatch();
stopWatch.Restart();
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());
}
}
}
|
