8

これが私が会計システムで作業しているように見える問題です。

私は一連のトランザクションを持っていますが、それらの合計は、経理部門がそうすべきだと考える金額と等しくありません。彼らは数学に疑問を投げかけているのではなく、含まれているのはトランザクションだけです：p

合計が特定の金額と一致するために、セット内のどのトランザクションを含めるべきでないかを判断するのに役立つアルゴリズムはありますか？

Given Set:  
2  
4  
5  
7

Given Sum Amount:
13

Result Set:
2
4
7

編集： セットに含まれるトランザクションは100未満です。XKCDの質問でNP完全問題を解くことに関するものがないので、誰かがC＃の例を持っていますか？

男、私はCSの学位を取得する必要がありました。

4

7 に答える 7

8

これはサブセット和問題であり、NP完全です。しかし、それはサブセット和を見つけるためのアルゴリズムがないという意味ではありません。

于 2009-07-29T19:43:45.443 に答える
7

これはナップサック問題であり、NP完全です。小さな入力セットを除いて、正確にそれを簡単に解決することはできません。まともなサイズの問題セットの場合、それは解決するための宇宙の寿命の問題の1つです。

とは言うものの、そこには遺伝的アルゴリズムのナップザックソルバーがあります。

于 2009-07-29T19:40:09.337 に答える
6

上記のメンバーが言ったように、これはサブセット和問題（またはナップサック問題）です。しかし、それを効率的に行うことができないと言うことはあまり正確ではありません。それは、多項式時間ではなく、実行できます。このソリューションは、動的計画法と再帰を使用して（そして疑似多項式時間で）実際には非常に単純です。

与えられた整数[a_1、...、a_n]と数T、

配列S[i、k]を定義して、a_1、...a_iの間に合計kになる要素のサブセットがあるかどうかを示します。（これはバイナリ行列です）。

次に、再帰的な関係を次のように定義できます。

S [i、k] = S [i-1、k]またはS [i-1、k-a_j]

つまり、これは、要素a_iを使用するか、使用しないかのどちらかであることを意味します。答えはS[n、T]にあります。

行列Sを作成するための作業負荷はどれくらいですか？さて、Sにはn*T要素があります。各要素を計算するには、O（1）の作業を行う必要があります。したがって、完全な実行時間はO（n * T）です。

さて、この時点で、これは多項式時間アルゴリズムのように見えるので、私はP=NPを証明したようです。ただし、入力サイズを2進数で測定するため、一部のpに対してT = 2^pであることに注意してください。

上記の解決策を適切に実装した場合、それが不合理であるとは誰も言わないと思います。実際、多くの妥当な問題サイズに対して、見事に機能します。

また、この問題を解決するためのヒューリスティックがいくつかありますが、私はその分野の専門家ではありません。

于 2009-07-29T20:07:34.840 に答える
3

わかった。多くの人が問題の名前を挙げており、NP困難について言及しています。そして、一般的に、それらは正しいです。ただし、解決する必要のある非常に特殊なケースがあります。最初に尋ねる質問は、100件のトランザクションが適切なものに近いと思うかどうかです。あなたにはいくつかの合計があります（「あなたの」合計）。彼らはいくつかの合計を持っています。（「実際の」合計）。したがって、一部の取引は偽物です。そこに偽のトランザクションがほんの少ししかないのではないかと疑うなら、これはそれほど悪くはありません。たとえば、偽のトランザクションが1つしかない場合を考えてみましょう。その場合、100個の異なる番号をチェックするだけで済みます。偽のトランスが2つある場合は、100 * 99の小切手を見ており、4つの偽のトランスでは、ほぼ1億ステップで物事が狂ってしまいます。でもあなたがすべてなら

もう1つの可能な近道は、データの性質を調べることです（ちなみに、100個の「数値」と予想される合計を投稿することは可能ですか？）。あなたの合計は実際の合計よりいくらですか？それらを削除すると、実際の合計よりも突然合計が低くなるほど大きな値はありますか？もしそうなら、あなたはそれらの値が偽の値であってはならないことを知っています。たとえば、あなたの例では、7が絶対に必要です。

于 2009-07-29T21:45:12.407 に答える
3

これはナップサック問題のバージョンです。NP完全であるため、一般的な良い答えは得られません。トランザクションのセットはどのくらいの大きさですか？あなたが示したようにそれは5ですか、それとも500のようですか？

于 2009-07-29T19:40:15.593 に答える
1 
        bool bBreak = false;
        int iEnd = 13;
        ArrayList ar1 = new ArrayList();
        ar1.Add(2);
        ar1.Add(4);
        ar1.Add(5);
        ar1.Add(7);

        String s1 = " ";
        foreach (int i in ar1)
        {
            if (i == iEnd)
            {
                s1 = "Result = " + i;
                bBreak = true;
            }
            if (bBreak) break;
            ArrayList ar2 = new ArrayList();
            ar2.AddRange(ar1);
            ar2.Remove(i);
            foreach (int j in ar2)
            {
                if ((i + j) == iEnd)
                {
                    s1 = "Results = " + i + ", " + j;
                    bBreak = true;
                }

                if (bBreak) break;
                ArrayList ar3 = new ArrayList();
                ar3.AddRange(ar2);
                ar3.Remove(j);
                foreach (int k in ar3)
                {
                    if (bBreak) break;
                    if ((i + j + k) == iEnd)
                    {
                        s1 = "Results = " + i + ", " + j + ", " + k;
                        bBreak = true;
                    }
                }
            }
        }
        Console.WriteLine(s1);
于 2011-08-02T15:46:36.183 に答える
1

はい、これは可能です。この投稿がまだ開いているかどうかわからない。ただし、Excelソルバーアドインを実行することをお勧めします。隣接するセルに1を付けて、すべての番号を投稿します。次に、目的の出力番号を入力します。次に、使用されているすべての番号が隣接する「1」を維持し、未使用の番号は「0」に変わります。次に、横に「1」が付いているものだけをリストするフィルター式を実行します。

于 2012-07-03T20:34:09.597 に答える