-1

重複の可能性：
特定の合計に達する可能性のある数字のすべての組み合わせを見つける

数値の配列から数値を選択するメソッドを作成する必要があります。その合計は必要な数値と正確に一致するか、存在しない場合は最小の大きい数値を選択します。この関数のアルゴリズムは何でしょうか?

public int[] selectExactSum(int[] X, int SUM) {
}

例: 数字は {5, 2, 8, 4, 6} で、必要な合計は 12 です。

結果は次のようになります: {2, 4, 6}

必要な合計が 13 の場合、結果は次のようになります:{2, 8, 4} - したがって、この場合、合計は 14 になります - 最初の最小の大きい方です。

必要な合計が 15 の場合、可能な結果は {5, 2, 8} または {5, 4, 6} になります。この場合、選択したものを返します。おそらく最初に取得したものです。

カスタム数値と合計のアルゴリズムは何ですか?

ありがとう、サイモン

4

3 に答える 3

6

これは、サブセット合計と呼ばれる問題の一般化されたケースです。これは NP 完全問題であるため、最もよく知られているアルゴリズムは疑似多項式です。上記のリンクされたアルゴリズムを理解していれば、問題を解決するために必要な変更を差し引くことができます。

于 2012-05-16T07:53:35.873 に答える
1

再帰的にはどうですか？

public static int[] SelectExactSum(int[] x, int sum) {
  int[]
    rest = x.Skip(1).ToArray(),
    with = x.Length == 1 ? x : x.Take(1).Concat(SelectExactSum(rest, sum - x[0])).ToArray(),
    without = x.Length == 1 ? new int[0] : SelectExactSum(rest, sum);
  int withSum = with.Sum(), withoutSum = without.Sum();
  return
    withSum >= sum ? (withoutSum >= sum ? (withSum < withoutSum ? with : without) : with) :
    withoutSum >= sum ? without : new int[0];
}

注: 呼び出しSelectExactSum(new int[] {5,2,8,4,6}, 13)は、質問に記載されているように {2,8,4} を返しませんが、実際には {5,8} を合計すると 13 になります。

于 2012-05-16T08:09:51.153 に答える
0

これを作成するのに約 15 分かかりました。ここで実行されていることがわかります。

http://jesuso.net/projects/selectExactSum/index.php?numbers=5%2C2%2C8%2C4%2C6&reqSum=15

コードは次のとおりです。

http://jesuso.net/projects/selectExactSum/selectExactSum.txt

できるだけシンプルにしましたが、PHP で作成されています。C# に翻訳するのに助けが必要な場合はお知らせください。

于 2012-05-16T08:21:41.960 に答える