Intereting Posts
Пропустить несколько параметров в действии controllerа Html.BeginForm MVC4 Другие способы обработки «инициализации цикла» в C # Запуск события изменения флажка в DataGridView Проблема с C # долларом с regex-replace Алгоритм Boyer-Moore-Horspool для всех совпадений (найти массив байтов внутри массива Byte) Интерфейс условного Builder Цепочный свободный интерфейс Запрос LINQ to SQL, где строка StartsWith элемент из общего списка NUnit сравнивает два списка Если Enum начинается с 0 или 1? Могу ли я использовать шаблон декоратора для обертывания тела метода? Запрос WWW / UnityWebRequest POST / GET не возвращает последние данные с сервера / URL-адреса Как определить и использовать ресурсы в xaml, чтобы их можно было использовать в C # Передача динамического объекта методу C # возвращает тип возврата Использование MediaCapture в настольном приложении Windows 8 Как использовать Ninject в приложении Windows Forms?

Найдите элементы в списке, которые вместе суммируют до целевого номера

Предположим, у меня есть список:

List _arr = new List {1, 3, 4}; 

И цель 4

Я хочу вернуть {1, 3} как 1 + 3 = 4 и {4} как 4 = 4 используя linq из данного списка.

Как я могу это сделать?

Это легко, если у нас есть способ получить все подмножества перечислителя / списка
(найти здесь: Ответ: Самый элегантный способ получить все подмножества массива в C # )

 using System; using System.Collections.Generic; using System.Linq; public static class Program { static void Main(string[] args) { var test = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; var target = 6; var matches = from subset in test.SubSetsOf() where subset.Sum() == target select subset; Console.WriteLine("Numbers: {0}", test.Select(i => i.ToString()).Aggregate((a, n) => a + ", " + n)); Console.WriteLine("Target: {0}", target); foreach (var match in matches) { Console.WriteLine(match.Select(m => m.ToString()).Aggregate((a, n) => a + " + " + n) + " = " + target.ToString()); } Console.ReadKey(); } public static IEnumerable> SubSetsOf(this IEnumerable source) { // Deal with the case of an empty source (simply return an enumerable containing a single, empty enumerable) if (!source.Any()) return Enumerable.Repeat(Enumerable.Empty(), 1); // Grab the first element off of the list var element = source.Take(1); // Recurse, to get all subsets of the source, ignoring the first item var haveNots = SubSetsOf(source.Skip(1)); // Get all those subsets and add the element we removed to them var haves = haveNots.Select(set => element.Concat(set)); // Finally combine the subsets that didn't include the first item, with those that did. return haves.Concat(haveNots); } } 

Выход:

 Numbers: 1, 2, 3, 4, 5, 6, 7, 8, 9 Target: 6 1 + 2 + 3 = 6 1 + 5 = 6 2 + 4 = 6 6 = 6 

Я считаю, что лучшим решением этой проблемы является динамическое программирование .

Создайте 2-мерный массив с размерами [a + 1, _arr.Length]:

  0 1 2 3 4 1 3 4 

Затем для каждого столбца в этом двумерном массиве заполните каждую ячейку, так что сумма всех ячеек столбца равна индексу столбца:

  0 1 2 3 4 1 0 1 x 0 1 3 0 0 x 1 1 4 0 0 x 0 0 // Alternative solution 0 1 2 3 4 1 0 1 x 0 0 3 0 0 x 1 0 4 0 0 x 0 1 

Здесь x означает, что решения нет. Кроме того, в столбце 4 есть 2 решения, поэтому вам нужно учитывать это, возможно, с помощью List[a] ?

Что касается того, как точно заполнить эти ячейки:
Столбец 0 будет содержать все нули, потому что это решение, которое может быть достигнуто без суммы.
Для столбца i вы хотите сделать i - n (где n – текущее число от _arr)

  0 1 1 0 1 // 1 - 1 == 0, so you put 1 in here 3 0 0 4 0 0 0 1 2 1 0 1 x // 2 - 1 == 1, 1 already has a solution, but you already used the number necessary to solve 1 3 0 0 x 4 0 0 x 

Если у вас было более 1 с

  0 1 2 1 0 1 1 // 1 - 1 == 0 1 0 0 1 // 2 - 1 == 1, 1 already has a solution 3 0 0 0 4 0 0 0 // Alternative solution 0 1 2 1 0 0 1 // 2 - 1 == 1, 1 already has a solution 1 0 1 1 // 1 - 1 == 0 3 0 0 0 4 0 0 0 

Если вам нужна дополнительная информация о динамическом программировании: « Задача« Рюкзак »Алгоритм динамического программирования

Я не думаю, что вы можете сделать это, используя простой запрос LINQ. На самом деле, я с трудом придумываю простое решение для этого, используя полномасштабный T-SQL!

Проблема в том, что вы пытаетесь вернуть не отдельные элементы, а различные коллекции элементов, основанные на возможных перестановках.

В этой заметке я надеюсь, что кто-то придумает такой запрос LINQ, потому что что-то говорит мне, что это будет потрясающе. 😉

Если вы после действительно хорошего и быстрого решения этой проблемы, вы не одиноки.

Это хорошо известная проблема SUBSET SUM. Я предлагаю вам ознакомиться с Википедии здесь:

http://en.wikipedia.org/wiki/Subset_sum_problem

Конечно, вы можете перебирать все возможные подмножества, ища свою сумму, но помните, что есть (2 ^ CountOfListElements) возможные комбинации. Если список всегда мал по размеру, у вас не будет проблем с его кодированием. Даже экспоненциальное временное решение будет работать для небольших наборов.