Could C# Linq do combinatorics?

问题:

I have this data structure:

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} }

I want to sum the Count properties of the collection and return only products objects where that property Count sum is less than or equal to 100.

If is not possible with linq, what is a better approach that I can use?

回答1:

Judging from the comments you've left on other peoples' answers and your gist (link), it looks like what you're trying to solve is in fact the Knapsack Problem - in particular, the 0/1 Knapsack Problem (link).

The Wikipedia page on this topic (that I linked to) has a short dynamic programming solution for you. It has pseudo-polynomial running time ("pseudo" because the complexity depends on the capacity you choose for your knapsack (W).

A good preprocessing step to take before running the algorithm is to find the greatest common denominator (GCD) of all of your item weights (w_i) and then divide it out of each value.

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

Then solve the problem using the modified weights and capacity instead (w_i' and W').

The greedy algorithm you use in your gist won't work very well. This better algorithm is simple enough that it's worth implementing.

回答2:

You need the Count extension method

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

EDIT:

If you want the sum of the items, Where and Sum extension methods could be utilized:

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

回答3:

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