制約のある 0/1 ナップサック問題の解決策を実装する必要があります。ほとんどの場合、私の問題には変数がほとんどありません (~ 10-20、最大で 50)。
多くの場合、ブルートフォースよりも優れたパフォーマンスを発揮する多くのアルゴリズムがあることを大学から思い出しました（たとえば、分枝限定アルゴリズムを考えています）。
私の問題は比較的小さいので、ブルートフォースとは対照的に洗練されたソリューションを使用すると、効率の点でかなりの利点があるかどうか疑問に思っています。
役に立ったら、私は Python でプログラミングしています。
重みの合計が十分に小さい場合は、動的計画法を使用する疑似多項式アルゴリズムを使用できます。X と Y ごとに最初の Y 項目で重み X を取得できるかどうかを計算するだけです。これは時間 O(NS) で実行されます。ここで、N は項目の数で、S は重みの合計です。
別の可能性は、中間アプローチを使用することです。アイテムを 2 つの半分に分割し、最初の半分では、アイテムのすべての可能な組み合わせ (各半分に 2^(N/2) の可能な組み合わせがあります) を取得し、その重みを何らかのセットに格納します。後半は考えられる組み合わせをすべて取り、前半に適切な重さの組み合わせがあるかどうかを確認します。これは O(2^(N/2)) 時間で実行されます。
ブルートフォース攻撃は10個の変数に対しては正常に機能しますが、たとえば40個の場合、1000'000'000'000の可能な解決策が得られ、列挙するには時間がかかりすぎる可能性があります。近似アルゴリズム、たとえば多項式時間アルゴリズム（たとえば、 http： //math.mit.edu/~goemans/18434S06/knapsack-katherine.pdfを参照）を検討するか、分枝限定法などの検索アルゴリズムを使用します。多分追加のヒューリスティックで。
ブルート フォース アルゴリズムは、常に最適なソリューションを返します。それらの問題は、指数関数的な順序の問題では、すぐに実行不可能になることです。
最大 20 個の変数を持つことが保証されている場合、100 万を超えるソリューションをテストすることはありません (2^20= 1M)。したがって、ブルート フォースが実行可能であり、他のアルゴリズムがより良いソリューションを返すことはありません。
ヒューリスティックは優れていますが、問題の正確な解決策がない場合にのみ使用する必要があります。あなたを助けるかもしれない素晴らしい本があります：それを解決する方法、ミハレヴィッチによる。