Может ли C# Linq делать комбинаторики?

Question

У меня есть эта структура данных:

class Product 
{ 
    public string Name { get; set; } 
    public int Count { get; set; } 
} 

var list = new List<Product>(){ { Name = "Book", Count = 40}, { Name = "Car", Count = 70}, { Name = "Pen", Count = 60}........... } // 500 product object 


var productsUpTo100SumCountPropert = list.Where(.....) ???? 

// productsUpTo100SumCountPropert output: 
// { { Name = "Book", Count = 40}, { Name = "Pen", Count = 60} } 

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

Если нет возможно ли с linq, что такое лучший подход, который я могу использовать?

Answer 1

Судя по комментариям, которые вы оставили в ответах других людей, и your gist (link), похоже, что вы пытаетесь решить, на самом деле проблема Рюкзак - в частности, 0/1 Knapsack Problem (link).

Страница Википедии на эту тему (с которой я связан) имеет для вас короткое решение для динамического программирования. Он имеет псевдо-полиномиальное время работы («псевдо», поскольку сложность зависит от мощности вы выбираете для вашего рюкзака (W).

Хороший шаг предварительной обработки принять перед запуском алгоритма, чтобы найти наибольший общий знаменатель (GCD) всех ваших весов элементов (w_i), а затем разделить его из каждого значения.

d <- GCD({w_1, w_2, ..., w_N}) 
w_i' <- w_i/d //for each i = 1, 2, ..., N 
W' <- W/d //integer division here 

Затем решить проблему с помощью модифицированных весов и мощности вместо (w_i' и W').

жадный алгоритм Эй u использование в вашем gist не будет работать очень хорошо. Этот лучший алгоритм достаточно прост, чтобы его можно было реализовать.

Answer 2

list.Where(p=> p.Count <= 100).ToList(); 

Answer 3

Вам нужно метод Count Extension

list.Count(p => p.Count <= 100); 

EDIT:

Если вы хотите, чтобы сумма элементов, Where и Sum методы расширения могут быть использованы:

list.Where(p => p.Count <= 100).Sum(p => p.Count);