Как использовать предложение where с условием sum в linq?

Question

Я хочу получить список из списка цен, где сумма значений равна значению, которое я хочу. Позвольте мне объяснить пример.

List<int> prices= new List{ 1, 2, 3, 4, 5 }; 
List<int> filteredList = GetSumList(4); // get list where the sum equals to 4, 1-3 or just 4. it doesn't matter which one. 

Как написать это GetSumList(int sum) функция.

Answer 1

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

public static IEnumerable<int> GetSumList(this IEnumerable<int> values, int sum) { 
    List<int>[] sets = new List<int>[sum+1]; 
    sets[0] = new List<int>(); 
    foreach(int xi in values) { //O(N*sum*N) with N the number of items 
     List<int> f0, f1, f2; 
     for(int i = sum-xi; i >= 0; i--) { //O(N*sum) 
      f0 = sets[i]; 
      f1 = sets[i+xi]; 
      if(f0 != null && (f1 == null || f0.Count < f1.Count-1)) { 
       f2 = new List<int>(f0);//make clone, O(N) 
       f2.Add(xi); 
       sets[i+xi] = f2; 
      } 
     } 
    } 
    return sets[sum]; 
} 

(если не существует такой суммы, null возвращается; этот алгоритм также вернет самый маленький поднабор, если таковой имеется).

Алгоритм использует динамическое программирование и рассматривает список комплектов. Каждый с отличной суммой . Вы можете сделать это немного быстрее, если вы используете связанный список вместо List<int> s при расчете временных значений, поскольку это позволяет (совместное) клонирование и вставки в голове в O (1).

Demo (с csharp интерактивной оболочки):

csharp> List<int> prices= new List<int>(new int[] { 1, 2, 3, 4, 5 }); 
csharp> prices.GetSumList(4);                
{ 4 } 
csharp> prices.GetSumList(6); 
{ 2, 4 } 
csharp> prices.GetSumList(7); 
{ 3, 4 } 
csharp> prices.GetSumList(8); 
{ 3, 5 } 
csharp> prices.GetSumList(9); 
{ 4, 5 } 
csharp> prices.GetSumList(10); 
{ 2, 3, 5 } 
csharp> prices.GetSumList(11); 
{ 2, 4, 5 } 
csharp> prices.GetSumList(12); 
{ 3, 4, 5 } 
csharp> prices.GetSumList(13); 
{ 1, 3, 4, 5 } 
csharp> prices.GetSumList(14); 
{ 2, 3, 4, 5 } 
csharp> prices.GetSumList(15); 
{ 1, 2, 3, 4, 5 } 
csharp> prices.GetSumList(16); 
null 

Answer 2

Если у вас есть списки списков вы можете сделать очень простой метод расширения LINQ, как так.

using System; 
using System.Linq; 
using System.Collections; 
using System.Collections.Generic; 


public class Test 
{ 
    public static void Main() 
    { 
     var lists = new List<List<int>> 
     { 
      new List<int> { 1, 2, 3 }, // 6 
      new List<int> { 3 }, // 3 
      new List<int> { 3, 3 }, // 6 
      new List<int> { 1, 2 }, // 3 
      new List<int> { 6 } // 6 
     }; 

     Console.WriteLine(lists.GetSumList(6).Count); // 3 
    } 
} 

public static class ListHelpers 
{ 
    public static List<List<int>> GetSumList(this List<List<int>> list, int sum) 
    { 
     return list.Where(x => x.Sum() == sum).ToList(); 
    } 
}