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
|
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 void AddAverage(Solution solution, int 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
{
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 = "Approx.", Func = SolveSubsetSum.Greedy };
static Problem Defaults = new Problem
{
NumItems = 100,
MinItemWeight = 1,
MaxItemWeight = 600,
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");
Solution averageDynamic = default(Solution);
Solution averageGreedy = default(Solution);
averageDynamic.Type = $"Average {Dynamic.Type}";
averageGreedy.Type = $"Average {Greedy.Type}";
File.WriteAllText(dynamicFile.FullName, "[Score @ Runtime]\n");
File.WriteAllText(greedyFile.FullName, "[Score @ Runtime]\n");
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);
dynamic.Output(dynamicFile);
greedy.Output(greedyFile);
}
File.AppendAllText(dynamicFile.FullName, "[Average]\n");
File.AppendAllText(greedyFile.FullName, "[Average]\n");
averageDynamic.Output(dynamicFile);
averageGreedy.Output(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 runtime = Stopwatch.StartNew();
var solution = algorithm.Func(items, capacity);
runtime.Stop();
return new Solution { Type = algorithm.Type, Value = solution, Runtime = runtime.Elapsed };
}
}
}
|
