-4

配列が : であるとします60,45,30,45,45,5,60,45,30,30,45,60,60,45,30,30,60,30,30。合計が 180 に等しい配列内の数値を見つける必要があります。複数の可能性は必要ありません。正しい選択は 1 つだけで十分です。ご覧のとおり、データ セットの値が繰り返される場合があります。ただし、データ セットが異なる場合があるため (より多くのサンプル)、操作全体が非常に効率的である必要があります。

4

5 に答える 5

5

数字を並べ替えます。合計より小さい値を繰り返し (重複をスキップして)、合計からそれぞれを順番に減算し、最後に選択された値の次の値から開始して、削減された合計を再帰的に解きます。(これにより、数字が昇順で表示されます。) 線形検索の代わりに二分検索を行うことで、最後の (4 番目の) レベル (正確な値を探している場合) を高速化できます。

たとえば、ソート後:

5,30,30,30,30,30,30,30,45,45,45,45,45,45,45,60,60,60,60,60
    try 5 and solve for 175:
        try 30 and solve for 145:
            try 30 and solve for 115: fail
            try 45 and solve for 100: fail 
            try 60 and solve for 85: fail
        try 45 and solve for 135:
            try 45 and solve for 95: fail
            try 60 and solve for 75: fail
        try 60 and solve for 115:
            try 60 and solve for 55: fail
    try 30 and solve for 150:
        try 30 and solve for 120:
            try 30 and solve for 90: fail
            try 45 and solve for 75: fail
            try 60 and solve for 60: success {30,30,60,60}

(すべての解を見つけたい場合は、成功にとどまらないでください。{30,45,45,60} もすぐに見つかります。)

于 2012-10-08T11:37:38.853 に答える
2

これは部分和問題の簡単な変形です。

任意のサイズのサブセットではなく、正確に4 つの要素を一緒に追加する必要があるという事実は、明らかに多項式時間で実行できることを意味します。

あなたの例から、配列内のすべての値が負ではないことがわかります。これにより、動的プログラミングまたは明示的な分岐限定 (おそらく DP アプローチとほぼ同じ作業になります) 、必ずしも同じ順序で行われるとは限りません)

于 2012-10-08T11:38:15.910 に答える
2 
var someEnumerable = new int[] { 60,45,30,45,45,5,60,45,30,30,45,60,60,45,30,30,60,30,30 };
var target = 200;
var solutions = from a1 in someenumerable
                from a2 in someenumerable
                from a3 in someenumerable
                from a4 in someenumerable
                let sum = a1 + a2 + a3 + a4
                where sum == target
                select new { a1, a2, a3, a4 };

var firstSolution = solutions.First();

Console.WriteLine("Possible solution: {0}, {1}, {2}, {3}", firstSolution.a1, firstSolution.a2, firstSolution.a3, firstSolution.a4);
于 2012-10-08T11:30:18.337 に答える
0

これは機能する可能性がありますが、解は 5 つ以上の数値で構成される場合があります。

 private void button1_Click(object sender, EventArgs e)
    {
        List<int> indexes = new List<int>();
        Calculate(180, 0, 0, array, indexes);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < indexes.Count; i++)
        {
            sb.Append(array[indexes[i]].ToString() + " [" + indexes[i].ToString() + "], ");
        }
        MessageBox.Show(sb.ToString());
    }

    bool Calculate(int goal, int sum, int index, int[] arr, List<int> indexes)
    {
        if (index > arr.Length - 1)
            return false;
        sum += arr[index];

        if (sum == goal)
        {
            indexes.Add(index);
            return true;
        }
        else if (sum > goal)
            return false;
        else
        {
            bool result = false;
            int count = 0;
            while (!(result = Calculate(goal, sum, index + ++count, arr, indexes)) && (index + count) < arr.Length) ;
            if (result)
            {
                indexes.Add(index);
                return true;
            }
            else
                return false;
        }

    }
于 2012-10-08T12:05:26.923 に答える
0

追加の条件（最大重量==（<=の代わりに）マジックナンバー）を使用すると、ナップザックの問題のように見えます。それを考えることができます。 http://en.wikipedia.org/wiki/Knapsack_problem

于 2012-10-08T11:32:33.507 に答える