خوارزمية للعثور على الأرقام من قائمة الحجم n sum إلى رقم آخر

Question

لدي رقم عشري (دعنا نسميه هدف) ومصفوفة من الأرقام العشرية الأخرى (دعنا نسمي المصفوفة عناصر) وأحتاج إلى العثور على جميع مجموعات الأرقام من عناصر الذي مجموع إلى الهدف.

لدي تفضيل للحل في C# (.Net 2.0) ولكن قد تفوز أفضل خوارزمية بغض النظر.

قد يبدو توقيع طريقتك كما يلي:

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

Answer 1

إجابات مثيرة للاهتمام.شكرًا لك على المؤشرات إلى ويكيبيديا - رغم أنها مثيرة للاهتمام - إلا أنها لا تحل المشكلة فعليًا كما هو مذكور كما كنت أبحث عن تطابقات تامة - فهي مشكلة موازنة/موازنة كتاب أكثر من مشكلة تعبئة الصناديق/حقيبة الظهر التقليدية.

لقد كنت أتابع باهتمام تطور تجاوز سعة المكدس وتساءلت عن مدى فائدته.ظهرت هذه المشكلة في العمل وتساءلت عما إذا كان تجاوز سعة المكدس يمكن أن يوفر إجابة جاهزة (أو إجابة أفضل) بشكل أسرع مما أستطيع كتابتها بنفسي.نشكرك أيضًا على التعليقات التي تقترح وضع علامة على هذا الواجب المنزلي - أعتقد أن هذا دقيق إلى حد معقول في ضوء ما ورد أعلاه.

بالنسبة لأولئك المهتمين، إليك الحل الذي يستخدم العودية (بشكل طبيعي). لقد غيرت رأيي أيضًا بشأن توقيع الطريقة وذهبت إلى القائمة> بدلاً من العلامة العشرية[]] كنوع الإرجاع:

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

يتم حل مشكلة المجموع الجزئي ومشكلة الحقيبة الأكثر عمومية باستخدام البرمجة الديناميكية:ليس من الضروري تعداد القوة الغاشمة لجميع المجموعات.راجع ويكيبيديا أو مرجع الخوارزميات المفضل لديك.

على الرغم من أن المسائل هي NP-كاملة، إلا أنها "سهلة" جدًا.التعقيد الخوارزمي في عدد العناصر منخفض.

Answer 3

أعتقد أن لديك مشكلة التعبئة بن على يديك (وهو أمر صعب NP)، لذلك أعتقد أن الحل الوحيد هو تجربة كل مجموعة ممكنة حتى تجد المجموعة التي تعمل.

يحرر:كما هو مذكور في التعليق، لن تفعل ذلك دائماً لديك لمحاولة كل مزيج ل كل مجموعة من الأرقام التي تصادفك.ومع ذلك، فإن أي طريقة تتوصل إليها تحتوي على مجموعات من الأرقام للسيناريو الأسوأ حيث يمكنك سوف لديك لمحاولة كل مجموعة - أو على الأقل مجموعة فرعية من المجموعات التي تنمو بشكل كبير مع حجم المجموعة.

وإلا فإنه لن يكون من الصعب 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);
    }
}