There are many Subset-sum questions and answers around at SO, but somehow I can't find a solution for my specific problem.
I need to find the quantity and length of track-segments to build a track of length n. The segments are of length: 8, 10, 12, 14, 16, 18, 20, 22, 24 ft The quantity can be up to 4 segments The track length is ~ between 20 and 100 ft. (and always an even number)
This is a real track. Order of segments does not matter. However, there are preferred size combinations. All of equal length or close to each other is preferred over Large/small combinations.
i.e:
- 70 => 20,20,20,10 would be an easy pick, but 16,18,18,18 would be preferred
- 60 => 20,20,20 is better then 14,14,14,18
I can trow on more examples if required.
I'm not looking for the one best solution, but a small set of possible best fit solution. Ultimately a person will choose, this is about suggestion best options.
What I did so far is the following. It is working, just seems way to complex.
I took the basic algorithm from this post Algorithm to find which numbers from a list of size n sum to another number. All I changed in this code is turn it into integer. It return all possible combinations. up to 5 or more tracks.
To further reduce result set, I do a few Linq's
List<int> nums = new List<int>() { 8, 8, 8, 8, 10, 10, 10, 10, 12, 12, 12, 12, 14, 14, 14, 14, 16, 16, 16, 16, 18, 18, 18, 18, 20, 20, 20, 20, 22, 22, 22, 22, 24, 24, 24, 24 };
int width = 60;
Console.WriteLine("Total width: " + width);
Solver solver = new Solver();
List<List<int>> res = solver.Solve(width, nums.ToArray());
Console.WriteLine("total :"+res.Count);
var res1 = res.Distinct(new SequenceComparer<List<int>, int>()).ToList();
Console.WriteLine("total res1:" + res1.Count);
var res2 = res1.Where(l => l.Count == 4).ToList();
Console.WriteLine("total res2:" + res2.Count); //reduce to 4 integer solutions
var res3 = (from row in res2
where row[0] == row[1] || row[0] == row[2] || row[0] == row[3] ||
row[1] == row[2] || row[1] == row[3] ||
row[2] == row[3]
select row).ToList();
Console.WriteLine("total res3:" + res3.Count); //reduce to at least two of equal length
var res4 = (from row in res3
where row[0] == row[1] && row[0] == row[2] ||
row[0] == row[1] && row[0] == row[3] ||
row[1] == row[2] && row[1] == row[3]
select row).ToList();
Console.WriteLine("total res4:" + res4.Count); //reduce to three of equal length
var res5 = (from row in res4
where row[0] == row[1] && row[0] == row[2] && row[0] == row[3]
select row).ToList();
Console.WriteLine("total res5:" + res5.Count); //reduce to 4 of equal length
Console.WriteLine("-------------------------------------");
Console.WriteLine("res4:");
foreach (List<int> result in res4)
{
foreach (int value in result)
{
Console.Write("{0}\t", value);
}
Console.WriteLine();
}
Console.WriteLine("-------------------------------------");
Console.WriteLine("res5:");
foreach (List<int> result in res5)
{
foreach (int value in result)
{
Console.Write("{0}\t", value);
}
Console.WriteLine();
}
Console.ReadLine();
This code will produce the following outcome, run with 60
Total width: 60
total :10726
total res1:74
total res2:31
total res3:20
total res4:3
total res5:0
-------------------------------------
res4:
12 12 12 24
12 16 16 16
14 14 14 18
-------------------------------------
res5:
or with 80 this
Total width: 80
total :101560
total res1:237
total res2:15
total res3:13
total res4:3
total res5:1
------------------------------------
res4:
8 24 24 24
14 22 22 22
20 20 20 20
------------------------------------
res5:
20 20 20 20
So my final results (4&5) are, in fact, close to what I need.
BUT I would have to code the same again for any possible 3 track solution, and maybe 2 tracks.
Then does results would need to be compared to each other (somehow, not sure how). ALL of this makes me feel like I am missing something. It feels to complex, it feels wrong. What am I missing?
AM I using the wrong algorithm to begin with? Are their better once out their for my problem?
