私は非常に迅速に実行されているソリューションを持っています。ただし、厳密なタイミングやメモリ チェックは行いませんでした。私のソリューションは再帰的ですが、動的にする方法はわかりません:
- N未満の配列で最大の数を見つけ、それをサブセットに追加します
ステップ 1 を再帰的に実行し、追加したばかりの数値を N から減算します
これにより、おそらく不完全な解決策が得られます
。N = 18、配列 = {12, 9, 8, 5, 4} の場合、{9, 5, 4} ではなくサブセットの回答 {12, 5} になります。このソリューションの「ギャップ」は であると言えますgap = 1。
サブセットの各メンバーmについて、N を に設定しm + gap、Array をサブセットのすべてのメンバーを除く元の配列のメンバーに設定して、再度解決します。この例では、N = 13、配列 = {9, 8, 4}、および N = 6、配列 = {9, 8, 4} という 2 つの問題が発生します。
ギャップ削減によって決定された、前のステップで提供された最適なソリューションを使用します。最適なソリューションのギャップがより大きな問題のギャップよりも小さい場合は、対象の数をサブセットに置き換えます。この場合、N = 13 は {9, 4} によって完全に解決され、12 を対象としているため、12 を {9, 4} に置き換えて {9, 4, 5} を取得します。
このサブ問題の場合gap=0は、これで完了です。
- に達しない
gap=0が置換を行った場合は、手順 4 を再帰します。
- 手順 4 で交換を行わなかった場合は、考えられる最善の解決策が得られたので、これで完了です。
私はかなり醜い C# でそれを行いましたが、コードが必要な場合は、少しクリーンアップできます。
編集：コードを追加
C# の詳細を特定の関数に限定しようとしました。常にソートしておく必要はありません。ImproveOnGaps 関数でメモリ使用量を削減できると確信しています。
走る：
void Main()
{
Problem p = Solvers.GenerateRandomProblem();
Solution imperfectSolution = Solvers.SolveRecursively(p);
Solution bestPossibleSolution = Solvers.ImproveOnGaps(s);
}
class Solution
{
public Problem Problem;
public int[] NumbersUsed;
public int n;
public int[] NumbersUnused;
}
class Problem
{
public int N;
public int[] Array;
}
class Solvers
{
public static Problem GenerateRandomProblem()
{
Random r = new Random();
int N = r.Next(1500000);
int arraySize = r.Next(1, 2000);
int[] array = new int[arraySize];
for(int i = 0; i < arraySize; i++)
array[i] = r.Next(1, 15000);
Problem problem = new Problem
{
N = N,
Array = array
};
return problem;
}
public static Solution SolveRecursively(Problem p)
{
return SolveRecursively( new Solution
{
Problem = p,
n = 0,
NumbersUnused = SortAscending(p.Array),
NumbersUsed = new int[0]
});
}
private static Solution SolveRecursively(Solution s)
{
if(s.n == s.Problem.N)
return s;
for(int i = s.NumbersUnused.Length - 1; i >= 0; i--) //
{
if(s.n + s.NumbersUnused[i] <= s.Problem.N)
{
return SolveRecursively(new Solution
{
n = s.n + s.NumbersUnused[i],
NumbersUnused = SkipIthPosition(s.NumbersUnused, i),
NumbersUsed = AddToSortedArray(s.NumbersUsed, s.NumbersUnused[i]),
Problem = s.Problem
});
}
}
return s;
}
public static Solution ImproveOnGaps(Solution s)
{
if(s.n == s.Problem.N)
return s;
int gap = s.Problem.N - s.n;
List<Problem> newProblems = new List<Problem>();
foreach (int i in s.NumbersUsed)
{
newProblems.Add(new Problem
{
Array = s.NumbersUnused,
N = i + gap
});
}
int newGap = gap;
Solution bestImprovement = null;
foreach (Problem p in newProblems)
{
Solution tempSolution = SolveRecursively(p);
if(tempSolution.Problem.N - tempSolution.n < newGap)
bestImprovement = tempSolution;
}
if(bestImprovement != null)
{
List<int> usedNumbers = s.NumbersUsed.ToList();
usedNumbers.Remove(bestImprovement.Problem.N - gap);
usedNumbers.AddRange(bestImprovement.NumbersUsed);
List<int> unusedNumbers = s.NumbersUnused.ToList();
foreach (int i in bestImprovement.NumbersUsed)
unusedNumbers.Remove(i);
return ImproveOnGaps(new Solution
{
n = usedNumbers.Sum(),
NumbersUnused = unusedNumbers.ToArray(),
NumbersUsed = usedNumbers.ToArray(),
Problem = s.Problem
});
}
return s;
}
private static int[] SortAscending(int[] array)
{
return array.OrderBy(i => i).ToArray();
}
private static int[] SkipIthPosition(int[] array, int i)
{
return array.Take(i)
.Union(array.Skip(i + 1).Take(array.Length - 1 - i))
.ToArray();
}
private static int[] AddToSortedArray(int[] array, int i)
{
return array.Concat(new int[] { i }).OrderBy(d => d).ToArray(),
}
}