Как вы должны это сделать, зависит от ряда важных вещей: сколько у вас будет чисел и насколько они будут большими? Кроме того, насколько я понимаю, ваши данные могут меняться (добавлять / удалять номера и т. Д.), Верно? Как часто вам нужно делать эти запросы?
Я представлю два решения. Я предлагаю вам использовать второе, так как я подозреваю, что это лучше для того, что вам нужно, и это намного легче понять.
Решение 1 - динамическое программирование
Пусть S[i] = true if we can make sum i and false otherwise.
S[0] = true // we can always make sum 0: just don't choose any number
S[i] = false for all i != 0
for each number i in your input
for s = MaxSum downto i
if ( S[s - i] == true )
S[s] = true; // if we can make the sum s - i, we can also make the sum s by adding i to the sum s - i.
Чтобы получить действительные числа, составляющие вашу сумму, вы должны оставить другой вектор P[i] = the last number that was used to make sum i. Вы обновите это соответствующим образом в условии if выше.
Временная сложность этого процесса O(numberOfNumbers * maxSumOfAllNumbers), что довольно плохо, особенно если учесть, что вам приходится перезапускать этот алгоритм при каждом изменении ваших данных. Это также медленно даже для одного запуска, пока ваши числа могут быть очень большими, и вы можете иметь их много. На самом деле, «много» вводит в заблуждение. Если у вас 100 номеров и каждое число может достигать 10 000, вы будете выполнять примерно 100 * 10 000 = 1 000 000 операций при каждом изменении данных.
Это хорошее решение, которое нужно знать, но не очень полезное на практике, или, по крайней мере, не в вашем случае, я думаю.
Он какой-то C # для подхода, который я предлагаю:
class Program
{
static void Main(string[] args)
{
List<int> testList = new List<int>();
for (int i = 0; i < 1000; ++i)
{
testList.Add(1);
}
Console.WriteLine(SubsetSum.Find(testList, 1000));
foreach (int index in SubsetSum.GetLastResult(1000))
{
Console.WriteLine(index);
}
}
}
static class SubsetSum
{
private static Dictionary<int, bool> memo;
private static Dictionary<int, KeyValuePair<int, int>> prev;
static SubsetSum()
{
memo = new Dictionary<int, bool>();
prev = new Dictionary<int, KeyValuePair<int, int>>();
}
public static bool Find(List<int> inputArray, int sum)
{
memo.Clear();
prev.Clear();
memo[0] = true;
prev[0] = new KeyValuePair<int,int>(-1, 0);
for (int i = 0; i < inputArray.Count; ++i)
{
int num = inputArray[i];
for (int s = sum; s >= num; --s)
{
if (memo.ContainsKey(s - num) && memo[s - num] == true)
{
memo[s] = true;
if (!prev.ContainsKey(s))
{
prev[s] = new KeyValuePair<int,int>(i, num);
}
}
}
}
return memo.ContainsKey(sum) && memo[sum];
}
public static IEnumerable<int> GetLastResult(int sum)
{
while (prev[sum].Key != -1)
{
yield return prev[sum].Key;
sum -= prev[sum].Value;
}
}
}
Возможно, вам следует выполнить некоторую проверку ошибок и, возможно, сохранить последнюю сумму в классе, чтобы не допустить возможности вызова GetLastResult с суммой, отличной от суммы, с которой Find последний раз вызывался. Во всяком случае, это идея.
Решение 2 - рандомизированный алгоритм
Теперь это проще. Держите два списка: usedNums и unusedNums. Также сохраните переменную usedSum, которая в любой момент времени содержит сумму всех чисел в списке usedNums.
Всякий раз, когда вам нужно вставить число в ваш набор, также добавьте его в один из двух списков (неважно, какой, но делайте это случайным образом, чтобы распределение было относительно равномерным). Обновите usedSum соответственно.
Всякий раз, когда вам нужно удалить номер из вашего набора, выясните, в каком из двух списков он находится. Вы можете сделать это с помощью линейного поиска, если у вас мало (на этот раз много означает более 10 000, возможно, даже 100 000 на быстром компьютере и при условии, что вы не выполняете эту операцию часто и в быстрой последовательности. В любом случае, линейный поиск может быть оптимизирован, если вам это нужно.). Как только вы нашли номер, удалите его из списка. Обновите usedSum соответственно.
Когда вам нужно найти, есть ли в вашем наборе числа, которые суммируют с числом S, используйте этот алгоритм:
while S != usedSum
if S > usedSum // our current usedSum is too small
move a random number from unusedNums to usedNums and update usedSum
else // our current usedSum is too big
move a random number from usedNums to unusedNums and update usedSum
В конце алгоритма список usedNums выдаст вам числа, сумма которых равна S.
Этот алгоритм должен быть хорош для того, что вам нужно, я думаю. Он очень хорошо обрабатывает изменения в наборе данных и хорошо работает для большого числа номеров. Это также не зависит от того, насколько большие числа, что очень полезно, если у вас большие числа.
Пожалуйста, пишите, если у вас есть какие-либо вопросы.