SOにはサブセットサムの質問と回答がたくさんありますが、どういうわけか私は特定の問題の解決策を見つけることができません.
長さ n のトラックを作成するには、トラック セグメントの数と長さを見つける必要があります。セグメントの長さ: 8, 10, 12, 14, 16, 18, 20, 22, 24 フィート 数量は最大 4 セグメントです トラックの長さは ~ 20 ～ 100 フィートです (常に偶数)
これは本物のトラックです。セグメントの順序は関係ありません。ただし、好ましいサイズの組み合わせがあります。大きい/小さい組み合わせよりも、すべて同じ長さまたは互いに近い方が優先されます。
すなわち:
- 70 => 20,20,20,10 は簡単に選択できますが、16,18,18,18 が優先されます
- 60 => 20,20,20 は 14,14,14,18 よりも優れています
必要に応じて、さらに例を挙げることができます。
私は 1 つの最適なソリューションを探しているのではなく、考えられる最適なソリューションの小さなセットを探しています。最終的には人が選択しますが、これは最良の選択肢の提案に関するものです。
これまでに行ったことは次のとおりです。それは機能していますが、複雑な方法のようです。
この投稿Algorithm to find which numbers from a list of a list of size n sum to another numberから基本的なアルゴリズムを採用しました。このコードで変更したのは、整数に変えることだけです。可能なすべての組み合わせを返します。5曲以上まで。
結果セットをさらに減らすために、いくつかのLinqを実行します
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();
このコードは次の結果を生成し、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:
または80でこれ
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
したがって、私の最終結果 (4&5) は、実際には必要なものに近いものです。
しかし、考えられる 3 トラック ソリューション、場合によっては 2 トラックについても、同じコードを再度コーディングする必要があります。
次に、結果を互いに比較する必要がありますか（どういうわけか、方法がわからない）。これらすべてが、何かが足りないような気がします。それは複雑に感じます、それは間違っていると感じます。私は何が欠けていますか？
そもそも間違ったアルゴリズムを使用していますか? 彼らは私の問題を解決するのに優れていますか？