Выбор предметов из списка для получения суммы

Question

У меня есть список элементов с числовыми значениями, и мне нужно получить сумму, используя эти элементы. Мне нужна ваша помощь, чтобы построить такой алгоритм. Ниже приведен пример, описывающий мою проблему, написанный на C #:

int sum = 21;

List<Item> list = new List<Item>();
list.Add(new Item() { Id = Guid.NewGuid(), Value = 3 });
list.Add(new Item() { Id = Guid.NewGuid(), Value = 5 });
list.Add(new Item() { Id = Guid.NewGuid(), Value = 12 });
list.Add(new Item() { Id = Guid.NewGuid(), Value = 3 });
list.Add(new Item() { Id = Guid.NewGuid(), Value = 2 });
list.Add(new Item() { Id = Guid.NewGuid(), Value = 7 });

List<Item> result = // the items in the list that has the defined sum.

Примечание: у меня нет ограничений на количество элементов в результате.

Answer 1

Это называется проблемой суммы подмножеств и считается сложной проблемой в информатике. Не сложно, как трудно, но трудно сделать быстро - вы можете легко написать алгоритм для этого, но для значительных входных данных это легко займет миллиарды лет.

Если вас устраивает медленное решение, которое возможно только для небольших входов, попробуйте что-то вроде этого:

• Создание всех подмножеств списка ввода.

• Для каждого поднабора вычислите сумму элементов в этом подмножестве.

• Возвращает первое подмножество, для которого совпадает сумма.

Вот метод, который возвращает все подмножества (на самом деле подпоследовательности , потому что он поддерживает порядок элементов, хотя в вашем случае это не имеет значения):

/// <summary>
/// Returns all subsequences of the input <see cref="IEnumerable&lt;T&gt;"/>.
/// </summary>
/// <param name="source">The sequence of items to generate
/// subsequences of.</param>
/// <returns>A collection containing all subsequences of the input
/// <see cref="IEnumerable&lt;T&gt;"/>.</returns>
public static IEnumerable<IEnumerable<T>> Subsequences<T>(
        this IEnumerable<T> source)
{
    if (source == null)
        throw new ArgumentNullException("source");
    // Ensure that the source IEnumerable is evaluated only once
    return subsequences(source.ToArray());
}

private static IEnumerable<IEnumerable<T>> subsequences<T>(IEnumerable<T> source)
{
    if (source.Any())
    {
        foreach (var comb in subsequences(source.Skip(1)))
        {
            yield return comb;
            yield return source.Take(1).Concat(comb);
        }
    }
    else
    {
        yield return Enumerable.Empty<T>();
    }
}

Так что теперь вы можете написать что-то вроде этого ...

var result = list.Subsequences()
                 .FirstOrDefault(ss => ss.Sum(item => item.Value) == sum);

Answer 2

Это называется проблемой суммы подмножеств с модификацией, которую вы хотите получить не до нуля, а до определенного числа.

Вот что Вики говорит об этом - http://en.wikipedia.org/wiki/Subset_sum_problem.

Вы можете подумать о некоторых оптимизациях в соответствии с вашими знаниями в области. Например, если наибольшее число + наименьшее число больше суммы -> наибольшее число никогда не будет использовано, и вы можете исключить его (и попробовать то же самое для нового наибольшего числа ...).

Я помню, как делал это, как предложил Самуэль, - рекурсивный способ, который не был таким уж ужасным (но, конечно, всегда есть проблема переполнения стека ...).

Answer 3

рекурсивно, добавляйте элементы до тех пор, пока А) не достигните суммы или Б) вы не получите слишком много, если А все готово, если Б вы измените элементы, пробуя все возможные конфигурации. Может быть, запретить системе добавлять элемент, если текущий элемент уже больше, чем последний элемент, который превысил сумму

Answer 4

Я не совсем уверен, какое солнце вы здесь после.Если вы хотите, чтобы сумма всех значений объединялась, используйте этот код:

int result = list.Sum( i => i.Value);

Если вы хотите, чтобы все элементы имели определенное значение, используйте этот код:

int x = 3;
List<Item> result = list.Where( i => i.Value == x);