この問題を可能にする 2 つの要因があります。
- 入力はサイズ O(sqrt(n)) に切り詰めることができます。負の入力がないため、100*sqrt(n) より大きい数値は破棄できます。また、すべての入力が異なるため、重要な入力は最大で 100*sqrt(n) であることがわかります。
- 競技場のサイズは O(sqrt(n)) です。重要な O(sqrt(n)) 入力を結合する O(2^sqrt(n)) 通りの方法がありますが、100*sqrt(n) の範囲を逸脱したり、重複してヒットしたりする組み合わせを気にする必要はありません。すでに到達できる目標。
基本的に、この問題は、「到達数」空間の各部分に対して各入力が何らかの形でチェックされる動的計画法を叫びます。
解決策は、(正しい方向にスキャンすることによって) 数値がそれ自体から離れないようにすること、各数値を 1 回だけ見ること、および後で解決策を再構築するのに十分な情報を自分自身に提供することの問題になります。
所定の時間内に問題を解決する C# コードを次に示します。
int[] FindSubsetToImpliedTarget(int[] inputs) {
var target = 100*(int)Math.Ceiling(Math.Sqrt(inputs.Count));
// build up how-X-was-reached table
var reached = new int?[target+1];
reached[0] = 0; // the empty set reaches 0
foreach (var e in inputs) {
// we go backwards to avoid reaching off of ourselves
for (var i = target; i >= e; i--) {
if (reached[i-e].HasValue) {
reached[i] = e;
}
}
}
// was target even reached?
if (!reached[target].HasValue) return null;
// build result by back-tracking via the logged reached values
var result = new List<int>();
for (var i = target; reached[i] != 0; i -= reached[i].Value) {
result.Add(reached[i].Value);
}
return result.ToArray();
}
上記のコードを実際にテストしたわけではないので、タイプミスやオフバイワンに注意してください。