c# - 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

他の人の回答と要点 (リンク)に残したコメントから判断すると、解決しようとしているのは実際にはナップザック問題、特に0/1 ナップザック問題 (リンク)のようです。

このトピックに関するウィキペディアのページ (リンク先) には、短い動的プログラミング ソリューションがあります。疑似多項式の実行時間があります (「疑似」は、ナップザックに選択した容量によって複雑さが異なるためです ( 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')。

要点で使用する貪欲なアルゴリズムはうまく機能しません。このより優れたアルゴリズムは、実装する価値があるほど単純です。

Answer 2

Count拡張メソッドが必要です

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

編集：

アイテムの合計が必要な場合はWhere、Sum拡張メソッドを利用できます。

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

Answer 3

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