كيفية العثور على ما الأرقام في مجموعة إضافة إلى آخر بالنظر إلى العدد ؟

Question

وهنا المشكلة التي يبدو أن تكون قيد التشغيل في العمل مع نظام للمحاسبة.

لدي مجموعة من المعاملات ، ولكن المبلغ لا يساوي المبلغ الذي قسم المحاسبة يعتقد أنه ينبغي.فهي لا أشكك في الرياضيات فقط المعاملات شملت :p

هل هناك خوارزمية التي من شأنها أن تساعدني في تحديد المعاملات في مجموعة لا ينبغي أن تدرج في المبلغ لتتناسب مع كمية معينة.

Given Set:  
2  
4  
5  
7

Given Sum Amount:
13

Result Set:
2
4
7

تحرير: هناك أقل من 100 المعاملات في المجموعة.لا أحد يملك C# على سبيل المثال كما لم يكن هناك أحد على حل NP-complete المشكلة في XKCD السؤال ؟

يا ليتني حصلت CS درجة.

Answer 1

هذا هو فرعية مبلغ المشكلة NP-Complete.ولكن هذا لا يعني انه ليس هناك خوارزمية لإيجاد مجموعة فرعية المبلغ.

Answer 2

هذا هو حقيبة المشكلة وانها NP-Complete.لن تحل بسهولة تماما مع أي شيء ما عدا صغيرة مجموعات الإدخال.أي لائق الحجم مشكلة تعيين, انها واحدة من تلك عمر من الكون إلى حل المشاكل.

وقال ان هناك الوراثية-خوارزمية حقيبة يحلون هناك.

Answer 3

كما سبق الأعضاء وقال: هذه هي مجموعة فرعية مبلغ المشكلة (أو حقيبة المشكلة).بيد أن أقول أنه لا يمكن القيام به بكفاءة ليست دقيقة جدا.ويمكن أن يتم ذلك فقط لا في وقت متعدد الحدود.الحل هو في الواقع بسيط جدا باستخدام البرمجة الديناميكية و العودية (وفي الزائفة وقت متعدد الحدود).

بالنظر إلى الأعداد الصحيحة [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 أو لا.الجواب سوف يكون موجودا في الصورة[n,T].

ما هو عبء العمل لبناء مصفوفة S ؟ حسنا, S n*T العناصر.لحساب كل عنصر ، يجب علينا أن نفعل O(1) العمل.حتى استكمال تشغيل الوقت O(n*T).

الآن عند هذه النقطة يبدو أنه قد ثبت P=NP ، وهذا يبدو أن الوقت متعدد الحدود الخوارزمية.ومع ذلك ، تذكر أن نقيس حجم المدخلات في الثنائية ، لذلك T = 2^p لبعض p.

لا أعتقد أن أحدا يقول أن الحل أعلاه, عندما نفذت بشكل غير معقول.في الواقع, العديد من معقولة المشكلة الأحجام ، وسوف تؤدي بشكل رائع.

أيضا هناك بعض الاستدلال على حل هذه المشكلة, ولكن أنا لست خبيرا في هذا المجال.

Answer 4

هذا هو نسخة من حقيبة المشكلة.إنه NP كاملة ، حتى أنك لن تحصل على عامة جيدة الإجابة.كيف كبيرة هي مجموعات من المعاملات ؟ هو 5 مثلك أظهر ، أو هو أكثر من 500?

Answer 5

موافق.الكثير من الناس قد أعطيت اسم المشكلة المذكورة كيف NP هو صعب .وفي عام ، فهي صحيحة.ومع ذلك لديك حالة خاصة تحتاج إلى حل.السؤال الأول الذي يطرح نفسه هو ما إذا كان أو لا كنت تعتقد 100 المعاملات أقرب إلى الحق منها.لديك بعض إجمالي ("بك" المجموع).لديهم بعض المجموع.("الحقيقي" المجموع).بعض المعاملات الخاصة بك ولذلك وهمية.إذا كنت تشك أن هناك فقط عدد قليل من الصفقات الوهمية في هناك ، ثم هذا ليس سيئا للغاية.على سبيل المثال, دعونا النظر في القضية حيث لا يوجد سوى واحد الصفقة وهمية.في هذه الحالة يجب ان يكون لديك فقط للتحقق 100 أرقام مختلفة.إذا كان هناك 2 وهمية عبر فأنت تبحث في 100*99 الشيكات, و سوف تحصل على جنون في 4 وهمية عبر, مع ما يقرب من 100,000,000 الخطوات.على الرغم من إذا كان كل ما تفعله هو إضافة بعض الباحث ليست رهيبة جدا.

آخر ممكن اختصار هو دراسة طبيعة البيانات الخاصة بك (بالمناسبة, هل من الممكن بعد 100 "أرقام" و المتوقع المبلغ؟).كم هو المبلغ الحقيقي المبلغ ؟ هل هناك أي قيم كبيرة بحيث القضاء عليها من شأنها أن تجعل الخاص بك مجموع فجأة أقل من المبلغ ؟ إذا كنت تعرف تلك القيم لا يمكن أن تكون وهمية منها.على سبيل المثال ، في سبيل المثال ، 7 هو المطلوب تماما.

Answer 6

        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);

Answer 7

نعم هذا ممكن.لست متأكدا إذا كان هذا المنصب هو لا يزال مفتوحا.ولكن كنت تريد أن تفعل Excel الوظيفة الإضافية Solver.بعد كل الأرقام مع 1s على الخلايا المجاورة.ثم وضع الإخراج المطلوب رقم..ثم جميع الأرقام المستخدمة ، سوف تبقى المجاورة لها "1" ، في حين غير المستخدمة منها سوف تتحول إلى "0".ثم القيام تصفية صيغة القوائم فقط تلك التي لديها "1" بجانبه.