サイズ n のリストからどの数値が別の数値と合計されるかを見つけるアルゴリズム

Question

私は 10 進数を持っています (そうしましょう) ゴール) と他の 10 進数の配列 (配列を呼びましょう) 要素) そして、次の数字の組み合わせをすべて見つける必要があります。 要素 合計が目標に達します。

私は C# (.Net 2.0) でのソリューションを好みますが、それに関係なく最良のアルゴリズムが勝つ可能性があります。

メソッドのシグネチャは次のようになります。

public decimal[][] Solve(decimal goal, decimal[] elements)

Answer 1

興味深い回答です。ウィキペディアへの指摘ありがとうございます - 興味深いものではありますが、私が正確に一致するものを探していたため、記載されているように実際には問題を解決するものではありません - 従来の箱詰め/ナップザックの問題というよりは、会計/帳簿のバランスの問題です。

私はスタック オーバーフローの開発を興味深く観察しており、これがどれほど役立つだろうかと考えていました。この問題は職場で生じたもので、スタック オーバーフローを使用すると、自分で作成するよりも早く、既製の答え (またはより良い答え) が得られるのではないかと疑問に思いました。これを宿題としてタグ付けすることを提案してくださったコメントにも感謝します。上記のことを考慮すると、それはかなり正確だと思います。

興味のある方のために、再帰を使用する私の解決策をここに示します (当然のことですが) メソッドのシグネチャについても考えを変え、戻り値の型として 10 進数 [][] ではなく List> を選択しました。

public class Solver {

    private List<List<decimal>> mResults;

    public List<List<decimal>> Solve(decimal goal, decimal[] elements) {

        mResults = new List<List<decimal>>();
        RecursiveSolve(goal, 0.0m, 
            new List<decimal>(), new List<decimal>(elements), 0);
        return mResults; 
    }

    private void RecursiveSolve(decimal goal, decimal currentSum, 
        List<decimal> included, List<decimal> notIncluded, int startIndex) {

        for (int index = startIndex; index < notIncluded.Count; index++) {

            decimal nextValue = notIncluded[index];
            if (currentSum + nextValue == goal) {
                List<decimal> newResult = new List<decimal>(included);
                newResult.Add(nextValue);
                mResults.Add(newResult);
            }
            else if (currentSum + nextValue < goal) {
                List<decimal> nextIncluded = new List<decimal>(included);
                nextIncluded.Add(nextValue);
                List<decimal> nextNotIncluded = new List<decimal>(notIncluded);
                nextNotIncluded.Remove(nextValue);
                RecursiveSolve(goal, currentSum + nextValue,
                    nextIncluded, nextNotIncluded, startIndex++);
            }
        }
    }
}

アプリでこれが機能することをテストしたい場合は、次のコンソール アプリ コードを試してください。

class Program {
    static void Main(string[] args) {

        string input;
        decimal goal;
        decimal element;

        do {
            Console.WriteLine("Please enter the goal:");
            input = Console.ReadLine();
        }
        while (!decimal.TryParse(input, out goal));

        Console.WriteLine("Please enter the elements (separated by spaces)");
        input = Console.ReadLine();
        string[] elementsText = input.Split(' ');
        List<decimal> elementsList = new List<decimal>();
        foreach (string elementText in elementsText) {
            if (decimal.TryParse(elementText, out element)) {
                elementsList.Add(element);
            }
        }

        Solver solver = new Solver();
        List<List<decimal>> results = solver.Solve(goal, elementsList.ToArray());
        foreach(List<decimal> result in results) {
            foreach (decimal value in result) {
                Console.Write("{0}\t", value);
            }
            Console.WriteLine();
        }


        Console.ReadLine();
    }
}

これが、他の人が（宿題かどうかにかかわらず）より早く答えを得るのに役立つことを願っています。

乾杯...

Answer 2

部分集合和問題と、もう少し一般的なナップザック問題は、動的計画法で解決されます。すべての組み合わせをブルートフォースで列挙する必要はありません。Wikipedia またはお気に入りのアルゴリズムのリファレンスを参照してください。

問題は NP 完全ですが、非常に「簡単な」NP 完全です。要素数におけるアルゴリズムの複雑さは低いです。

Answer 3

持っていると思います ビンの梱包の問題 なので、唯一の解決策は、うまくいく組み合わせが見つかるまで、考えられるすべての組み合わせを試すことだと思います。

編集：コメントで指摘されているように、そうではありません いつも 試してみなければなりません 毎 の組み合わせ 毎 遭遇した数字のセット。ただし、どの方法を考え出しても、最悪のシナリオの数値セットが存在します。 意思 試してみなければなりません 毎 組み合わせ -- または、セットのサイズに応じて指数関数的に増加する少なくとも組み合わせのサブセット。

そうでなければNP難にはならない。

Answer 4

あなたは次のことを説明しました ナップサック問題, 、唯一の本当の解決策はブルートフォースです。より高速な近似解がいくつかありますが、ニーズに合わない可能性があります。

Answer 5

(他の人がすでに述べたように) ブルートフォースの問題は解決しませんが、最初に数値を並べ替えてから、残っている可能性のある数値を検討することをお勧めします (Sum 値を渡すと、Goal より大きい数値を追加することはできないため)。和）。

これにより、アルゴリズムの実装方法が変わります (一度だけ並べ替えて、マークされた要素をスキップするため) が、平均するとパフォーマンスが向上します。

Answer 6

public class Logic1 {
    static int val = 121;
    public static void main(String[] args)
    {
        f(new int[] {1,4,5,17,16,100,100}, 0, 0, "{");
    }

    static void f(int[] numbers, int index, int sum, String output)
    {
        System.out.println(output + " } = " + sum);
        //System.out.println("Index value1 is "+index);
        check (sum);
        if (index == numbers.length)
        {
            System.out.println(output + " } = " + sum);
            return;
        }

        // include numbers[index]
        f(numbers, index + 1, sum + numbers[index], output + " " + numbers[index]);
        check (sum);
        //System.out.println("Index value2 is "+index);
        // exclude numbers[index]
        f(numbers, index + 1, sum, output);
        check (sum);
    }

    static void check (int sum1)
    {
        if (sum1 == val)
            System.exit(0);
    }
}