algorithm - 配列内の整数の最大合計を見つけるが、x より大きくない

Question

整数の配列があるとしましょう:

int array = {5, 7, 4, 4, 2}
int x=10

出力は次のようになります。

10 //(4,4,2)

この出力を達成するための最速の方法は何ですか?

Answer 1

サブセット合計問題を扱っています (連続したサブ配列が必要ないと仮定します)。

問題はNP-Completeであり、それに対する既知の多項式解はありません (そして、一般的な仮定は、存在しないということですが、まだ証明されていません) 。

ただし、動的計画法を使用した疑似多項式ソリューションがあります。

Answer 2

あなたが求めている問題は、

0-1 Knapsack problem

ここで、利益は重量と同じです。

あなたはそれをグーグルしてアルゴリズムを簡単に理解することができます。これはおそらく最速の方法です。