サイズ n の数のセットがあります (n > 100 と仮定)。
ハードリミット x もあります。
私が望むのは、セットから可変数の要素を取得し、これらの要素の組み合わせを見つけて、合計すると合計が <= x になるようにすることですが、可能な限り x に近づけることです。
明らかに私はブルートフォースアプローチをしたくありません.この問題を解決する効率的なアルゴリズムはありますか?
1 に答える
1
これは、頻繁に使用される疑似多項式ナップザック アルゴリズムに完全に適しているようです。このアルゴリズムについては、既にお持ちのテキストで説明されているか、この PDFの 41 ページで入手できます。
于 2012-07-13T21:28:03.897 に答える