C#Linq可以组合吗? [英] Could C# Linq do combinatorics?

问题描述

我有这个数据结构:

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 sum小于或等于100的产品对象.

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.

如果linq无法实现，那么我可以使用哪种更好的方法呢?

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

推荐答案

从您对其他人的答案和

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).

这个主题的Wikipedia页面(我链接到该页面)为您提供了一个简短的动态编程解决方案.它具有伪多项式运行时间("pseudo"，因为复杂度取决于您为背包(W)选择的容量.

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).

在运行算法之前，一个好的预处理步骤是找到所有项目权重(w_i)的最大公分母(GCD)，然后将其除以每个值.

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

然后使用修改后的权重和容量(w_i'和W')解决问题.

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.

这篇关于C#Linq可以组合吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！