[Vlad Drakula]

ivank
собственно ваш алгоритм не всегда корректно работат...
Всё хорошо, путь: 10 2 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19 20 = 400

int l = 20;
summ2(m,l, l*l);

[ivank]

Vlad Drakula
Влад. Ты неправильно переделал мой код в C#. И не взял мою исправленную функцию из предыдущего поста. Давай помедитируем над разницей вот этого:

static void summ2(int[] num, int n, int m) { int[] way = new int[m+1]; for (int i = 0; i <= m; ++i) way[i] = 0;

и вот этого:

static void summ2(int[] num, int n, int size) { int m = n*(n+1)/2-1; // сумма всех чисел, кроме первого int[] way = new int[m+1]; for (int i = 0; i <= m; ++i) way[i] = 0;

Чуешь разницу? Не вали свои баги на меня. В исправленом коде случае. summ2(m, l, l*l); даёт именно "Всё плохо". Всё за те же 4 секунды. В то время, как твой код на аналогичном тесте вешается (при достаточно больших l, 100 уже более чем достаточно).

Ну и вот очередной тест. Сортировка не поможет. У меня всё те же несколько секунд. (Впредь прошу при тестах моего кода брать мою версию, а не то, что ты криво сконвертировал).

Всего 100 чисел. мой код - 0.08с, понятно что зависимость от l - квадратичная, так что при 1000 числах (в 10 раз больше) уже будет ~10с (в 100 раз дольше). Вуаля:

Код:

using System;

namespace summ
{
    class Class1
    {
        static bool su(int[] m, int[] s, int i, int p, int l, int size, int corsize)
        {
            for(;i < l; i++)
            {
                if(corsize + m[i] == size)
                {
                    for(int j = 0; j <= p; j ++)
                    {
                        Console.Write("{0} + ", m[s[j]]);
                    }

                    Console.WriteLine("{0} = {1};", m[i], size);

                    return true;
                }
                else if(corsize + m[i] < size)
                {
                    s[p + 1] = i;
                    if(su(m, s, i + 1, p + 1, l, size, corsize + m[i]))
                    {
                        return true;
                    }
                }
            }

            return false;
        }

        static void QSort(int[] ar, int size)
        {
            int left, right, ixLeft, ixRight;
            int[] borderLeft = new int[100];
            int[] borderRight = new int[100];
            int stach = 0;
            int copy;
            int x;
            Random r = new Random();
            borderLeft[0] = 0;
            borderRight[0] = size - 1;
            while(stach >= 0)
            {
                ixLeft = left = borderLeft[stach];
                ixRight = right = borderRight[stach];
                stach--;
                
                while(left < right)
                {
                    x = ar[r.Next(left, right)];
                    ixLeft = left;
                    ixRight = right;

                    while(ixLeft <= ixRight)
                    {
 
                        while(ar[ixLeft] > x)
                        {
                            ixLeft++;
                        }
                        while(ar[ixRight] < x)
                        {
                            ixRight--;
                        }
                    
                        if(ixLeft <= ixRight)
                        {
                            copy = ar[ixLeft];
                            ar[ixLeft] = ar[ixRight];
                            ar[ixRight] = copy;
                            ixLeft++;
                            ixRight--;
                        }
                    }

                    if(ixRight - left < right - ixLeft)
                    {
                        stach++;
                        borderLeft[stach] = ixLeft;
                        borderRight[stach] = right;
                        right = ixRight;
                    }
                    else
                    {
                        stach++;
                        borderLeft[stach] = left;
                        borderRight[stach] = ixRight;
                        left = ixLeft;
                    }
                }                
            }
        }

        static void summ(int[] m, int l, int size)
        {
            QSort(m, l);
            int[] s = new int[l];
            su(m, s, 0, -1, l, size, 0);            
        }

        static void summ2(int[] num, int n, int m)
        {
            int[] way = new int[m+1];
            for (int i = 0; i <= m; ++i)
                way[i] = 0;

            way[0] = 1;

            for (int i = 0; i < n; ++i)
                for (int j = m; j > 0; --j)
                    if (way[j] == 0 && j >= num[i] && way[j-num[i]] != 0)
                        way[j] = num[i];

            if (way[m] == 0)
                Console.WriteLine("Всё плохо");
            else
            {
                Console.Write("Всё хорошо, путь: ");
                for (int i = m; i != 0; i -= way[i])
                    Console.Write("{0} ", way[i]);
                Console.WriteLine("");
            }
        }

        static void Main(string[] args)
        {
            DateTime d1, d2;
            int l = 100;
            int[] m = new int[l];

	    int needed = 0;

            for(int j = 0; j < l; j++)
            {
                m[j] = l+j+1;
                needed += m[j];
            }
            needed -= m[l/2];

            d1 = DateTime.Now;                
            summ2(m, l, needed);
            d2 = DateTime.Now;
            Console.WriteLine("ivank's time: {0}", d2 - d1);

            d1 = DateTime.Now;                
            summ(m, l, needed);
            d2 = DateTime.Now;
            Console.WriteLine("vlad's time: {0}", d2 - d1);
        }
    }
}

Кстати, я вспомнил. Это называется задачей об укладке рюкзака, частный её случай. Это NP-полная задача в общем случае. Её можно решить за "псевдо-полиномиальное" время, что я и делаю. предлагаю просесть всю статью.

Честно гворя, я считал, что в СпбГУ достаточно высокий уровень образования, что бы знать комбинаторику в объёме достаточном для понимания, что для перебора всех комбинаций из n чисел требуется 2^n операций. И что это очень большое число уже при n порядка 30.

[Vlad Drakula]

ivank
приношу извинения за недогляд при портировании...

предлагаю перейти в тестах на рандомные наборы чисел...

PHP код:

using System;



namespace summ

{

    class Class1

    {

        static int su(int[] m, int[] s, int i, int p, int l, int size, int corsize)

        {

            for(int r = 0;i < l; i++, r++)

            {

                if(corsize + m[i] == size)

                {

                    for(int j = 0; j <= p; j ++)

                    {

                        Console.Write("{0} + ", m[s[j]]);

                    }



                    Console.WriteLine("{0} = {1};", m[i], size);



                    return 0;

                }

                else if(corsize + m[i] < size)

                {

                    if(i + 1 == l)

                    {

                        return r == 0 ? -1 : 1;

                    }



                    s[p + 1] = i;



                    switch(su(m, s, i + 1, p + 1, l, size, corsize + m[i]))

                    {

                        case 0:

                            return 0;



                        case -1:

                            if(r == 0)

                            {

                                return -1;

                            }

                            break;



                        case 1:

                            r = 1;

                            break;

                    }

                }

                else if(i + 1 == l)

                {

                    return 1;

                }                

            }



            return 1;

        }



        static void QSort(int[] ar, int size)

        {

            int left, right, ixLeft, ixRight;

            int[] borderLeft = new int[100];

            int[] borderRight = new int[100];

            int stach = 0;

            int copy;

            int x;

            Random r = new Random();

            borderLeft[0] = 0;

            borderRight[0] = size - 1;

            while(stach >= 0)

            {

                ixLeft = left = borderLeft[stach];

                ixRight = right = borderRight[stach];

                stach--;

                

                while(left < right)

                {

                    x = ar[r.Next(left, right)];

                    ixLeft = left;

                    ixRight = right;



                    while(ixLeft <= ixRight)

                    {

 

                        while(ar[ixLeft] > x)

                        {

                            ixLeft++;

                        }

                        while(ar[ixRight] < x)

                        {

                            ixRight--;

                        }

                    

                        if(ixLeft <= ixRight)

                        {

                            copy = ar[ixLeft];

                            ar[ixLeft] = ar[ixRight];

                            ar[ixRight] = copy;

                            ixLeft++;

                            ixRight--;

                        }

                    }



                    if(ixRight - left < right - ixLeft)

                    {

                        stach++;

                        borderLeft[stach] = ixLeft;

                        borderRight[stach] = right;

                        right = ixRight;

                    }

                    else

                    {

                        stach++;

                        borderLeft[stach] = left;

                        borderRight[stach] = ixRight;

                        left = ixLeft;

                    }

                }                

            }

        }



        static bool summ(int[] m, int l, int size)

        {

            QSort(m, l);

            int[] s = new int[l];

            return su(m, s, 0, -1, l, size, 0) == 0 ? true : false;        

        }



        static bool summ2(int[] num, int n, int size)

        {

            int m = size;



            int[] way = new int[m+1];

            for (int i = 0; i <= m; ++i)

                way[i] = 0;



            way[0] = 1;



            for (int i = 0; i < n; ++i)

                for (int j = m; j > 0; --j)

                    if (way[j] == 0 && j >= num[i] && way[j-num[i]] != 0)

                        way[j] = num[i];



            if (way[m] == 0)

            {

                Console.WriteLine("Всё плохо");

                return false;

            }

            Console.Write("Всё хорошо, путь: ");

            for (int i = m; i != 0; i -= way[i])

            {

                Console.Write("{0} ", way[i]);

            }

            Console.WriteLine(" = {0}", size);

            

            return true;

        }



        static void Main(string[] args)

        {

            DateTime d1, d2;

            int l = 2000;

            int[] m = new int[l];



            Random r = new Random();

            for (int j = 0; j < l; ++j)

            {

                m[j] = r.Next(10, 1000);

            }

            int needed = r.Next(10 * l / 3, 1000 * l / 3);

    

            d1 = DateTime.Now;                

            summ2(m,l, needed);

            d2 = DateTime.Now;

            Console.WriteLine("ivank's time: {0}", d2 - d1);



            d1 = DateTime.Now;                

            summ(m,l, needed);

            d2 = DateTime.Now;

            Console.WriteLine("vlad's time: {0}", d2 - d1);

        }

    }

} 

ivank's time: 00:00:11.3763584
vlad's time: 00:00:00.0200288

[ivank]

Vlad Drakula

предлагаю перейти в тестах на рандомные наборы чисел...

Слив засчитан.

Я показал, что твой алгоритм в некоторых случаях подвисает (например, когда требуемой комбинации не существует. А такое в оригинальной поставновке задачи может быть). Этого достаточно, чтобы его нельзя было применять. Мой алгоритм [i]гарантированно[i] работает всегда за O(m*n), что в оригинальной постановке задачи (n ~ 40, m ~300000) означает не более чем секундную задержку. Секундная задержка лучше, чем возможное подвисание.

Более того. Предлагаю просто протестировать на реальных данных оба метода. Реальные данные - пример от автора, в посте номер 8.

ivank's time: 00:00:00.2220340 vlad's time: 00:00:13.5698600

что в общем-то и требовалось доказать: в общем случае твой метод нерпиемлем. Более того, если needed=349963, то он опять же подвисает. Да, у тебя достаточно хорошая эвристика, чтобы при достаточно большом наборе чисел рапределённых равномерно быстро находить требуемую комбинацию. К сожалению, входные наборы далеко не всегда обладают такими характеристиками.

Аналогично мой метод ограничен произведением m*n. Но как раз в исходной постановке - это не проблема. А вот возможное отсутствие требуемой комбинации -- очень даже.

Код:

using System;

namespace summ
{
    class Class1
    {
        static int su(int[] m, int[] s, int i, int p, int l, int size, int corsize)
        {
            for(int r = 0;i < l; i++, r++)
            {
                if(corsize + m[i] == size)
                {
                    for(int j = 0; j <= p; j ++)
                    {
                        Console.Write("{0} + ", m[s[j]]);
                    }

                    Console.WriteLine("{0} = {1};", m[i], size);

                    return 0;
                }
                else if(corsize + m[i] < size)
                {
                    if(i + 1 == l)
                    {
                        return r == 0 ? -1 : 1;
                    }

                    s[p + 1] = i;

                    switch(su(m, s, i + 1, p + 1, l, size, corsize + m[i]))
                    {
                        case 0:
                            return 0;

                        case -1:
                            if(r == 0)
                            {
                                return -1;
                            }
                            break;

                        case 1:
                            r = 1;
                            break;
                    }
                }
                else if(i + 1 == l)
                {
                    return 1;
                }                
            }

            return 1;
        }

        static void QSort(int[] ar, int size)
        {
            int left, right, ixLeft, ixRight;
            int[] borderLeft = new int[100];
            int[] borderRight = new int[100];
            int stach = 0;
            int copy;
            int x;
            Random r = new Random();
            borderLeft[0] = 0;
            borderRight[0] = size - 1;
            while(stach >= 0)
            {
                ixLeft = left = borderLeft[stach];
                ixRight = right = borderRight[stach];
                stach--;
                
                while(left < right)
                {
                    x = ar[r.Next(left, right)];
                    ixLeft = left;
                    ixRight = right;

                    while(ixLeft <= ixRight)
                    {
 
                        while(ar[ixLeft] > x)
                        {
                            ixLeft++;
                        }
                        while(ar[ixRight] < x)
                        {
                            ixRight--;
                        }
                    
                        if(ixLeft <= ixRight)
                        {
                            copy = ar[ixLeft];
                            ar[ixLeft] = ar[ixRight];
                            ar[ixRight] = copy;
                            ixLeft++;
                            ixRight--;
                        }
                    }

                    if(ixRight - left < right - ixLeft)
                    {
                        stach++;
                        borderLeft[stach] = ixLeft;
                        borderRight[stach] = right;
                        right = ixRight;
                    }
                    else
                    {
                        stach++;
                        borderLeft[stach] = left;
                        borderRight[stach] = ixRight;
                        left = ixLeft;
                    }
                }                
            }
        }

        static bool summ(int[] m, int l, int size)
        {
            QSort(m, l);
            int[] s = new int[l];
            return su(m, s, 0, -1, l, size, 0) == 0 ? true : false;        
        }

        static bool summ2(int[] num, int n, int size)
        {
            int m = size;

            int[] way = new int[m+1];
            for (int i = 0; i <= m; ++i)
                way[i] = 0;

            way[0] = 1;

            for (int i = 0; i < n; ++i)
                for (int j = m; j > 0; --j)
                    if (way[j] == 0 && j >= num[i] && way[j-num[i]] != 0)
                        way[j] = num[i];

            if (way[m] == 0)
            {
                Console.WriteLine("Всё плохо");
                return false;
            }
            Console.Write("Всё хорошо, путь: ");
            for (int i = m; i != 0; i -= way[i])
            {
                Console.Write("{0} ", way[i]);
            }
            Console.WriteLine(" = {0}", size);
            
            return true;
        }

        static void Main(string[] args)
        {
            DateTime d1, d2;
            int l = 42;
            int[] m = {
                197900,70584,65006,39893,27638,
                29448,17220,7750,39032,2870,
                2010,22386,93275,20090,10906,
                36162,4133,40180,64575,34440,
                6027,8754,22960,4879,22960,
                18311,39893,27638,58896,24108,
                22386,2727,36162,4879,4133,
                34440,5740,2727,15355,1665,
                34440,8610
            };

            int needed = 350000; // Попробуй 349963
    
            d1 = DateTime.Now;                
            summ2(m,l, needed);
            d2 = DateTime.Now;
            Console.WriteLine("ivank's time: {0}", d2 - d1);

            d1 = DateTime.Now;                
            summ(m,l, needed);
            d2 = DateTime.Now;
            Console.WriteLine("vlad's time: {0}", d2 - d1);
        }
    }
}

[ivank]

P.P.S. последний кусочек статистики.
int[] m = {
197900,70584,65006,39893,27638,
29448,17220,7750,39032,2870,
2010,22386,93275,20090,10906,
36162,4133,40180,64575,34440,
6027,8754,22960,4879,22960,
18311,39893,27638,58896,24108,
22386,2727,36162,4879,4133,
34440,5740,2727,15355,1665,
34440,8610
};
Максимальная сумма - 1233188. При этом невозможно получить 306002 различных сумм с помощью данного набора. То есть, если выбирать needed случайно, с вероятностью 1/4 твоя программа зависнет.

Код:

using System;

namespace summ
{
    class Class1
    {
        static int su(int[] m, int[] s, int i, int p, int l, int size, int corsize)
        {
            for(int r = 0;i < l; i++, r++)
            {
                if(corsize + m[i] == size)
                {
                    for(int j = 0; j <= p; j ++)
                    {
                        Console.Write("{0} + ", m[s[j]]);
                    }

                    Console.WriteLine("{0} = {1};", m[i], size);

                    return 0;
                }
                else if(corsize + m[i] < size)
                {
                    if(i + 1 == l)
                    {
                        return r == 0 ? -1 : 1;
                    }

                    s[p + 1] = i;

                    switch(su(m, s, i + 1, p + 1, l, size, corsize + m[i]))
                    {
                        case 0:
                            return 0;

                        case -1:
                            if(r == 0)
                            {
                                return -1;
                            }
                            break;

                        case 1:
                            r = 1;
                            break;
                    }
                }
                else if(i + 1 == l)
                {
                    return 1;
                }                
            }

            return 1;
        }

        static void QSort(int[] ar, int size)
        {
            int left, right, ixLeft, ixRight;
            int[] borderLeft = new int[100];
            int[] borderRight = new int[100];
            int stach = 0;
            int copy;
            int x;
            Random r = new Random();
            borderLeft[0] = 0;
            borderRight[0] = size - 1;
            while(stach >= 0)
            {
                ixLeft = left = borderLeft[stach];
                ixRight = right = borderRight[stach];
                stach--;
                
                while(left < right)
                {
                    x = ar[r.Next(left, right)];
                    ixLeft = left;
                    ixRight = right;

                    while(ixLeft <= ixRight)
                    {
 
                        while(ar[ixLeft] > x)
                        {
                            ixLeft++;
                        }
                        while(ar[ixRight] < x)
                        {
                            ixRight--;
                        }
                    
                        if(ixLeft <= ixRight)
                        {
                            copy = ar[ixLeft];
                            ar[ixLeft] = ar[ixRight];
                            ar[ixRight] = copy;
                            ixLeft++;
                            ixRight--;
                        }
                    }

                    if(ixRight - left < right - ixLeft)
                    {
                        stach++;
                        borderLeft[stach] = ixLeft;
                        borderRight[stach] = right;
                        right = ixRight;
                    }
                    else
                    {
                        stach++;
                        borderLeft[stach] = left;
                        borderRight[stach] = ixRight;
                        left = ixLeft;
                    }
                }                
            }
        }

        static bool summ(int[] m, int l, int size)
        {
            QSort(m, l);
            int[] s = new int[l];
            return su(m, s, 0, -1, l, size, 0) == 0 ? true : false;        
        }

        static bool summ2(int[] num, int n, int size)
        {
            int m = size;

            int[] way = new int[m+1];
            for (int i = 0; i <= m; ++i)
                way[i] = 0;

            way[0] = 1;

            for (int i = 0; i < n; ++i)
                for (int j = m; j > 0; --j)
                    if (way[j] == 0 && j >= num[i] && way[j-num[i]] != 0)
                        way[j] = num[i];
        
	    if (way[m] == 0)
            {
                Console.WriteLine("Всё плохо");
                return false;
            }
            Console.Write("Всё хорошо, путь: ");
            for (int i = m; i != 0; i -= way[i])
            {
                Console.Write("{0} ", way[i]);
            }
            Console.WriteLine(" = {0}", size);
            
            return true;
        }

        static void Main(string[] args)
        {
            DateTime d1, d2;
            int l = 42;
            int[] m = {
                197900,70584,65006,39893,27638,
                29448,17220,7750,39032,2870,
                2010,22386,93275,20090,10906,
                36162,4133,40180,64575,34440,
                6027,8754,22960,4879,22960,
                18311,39893,27638,58896,24108,
                22386,2727,36162,4879,4133,
                34440,5740,2727,15355,1665,
                34440,8610
            };
            Random r = new Random();
            while (true)
            {
                int needed = r.Next(1665, 1233188);

                d1 = DateTime.Now;                
                summ2(m,l, needed);
                d2 = DateTime.Now;
                Console.WriteLine("ivank's time: {0}", d2 - d1);

                d1 = DateTime.Now;                
                summ(m,l, needed);
                d2 = DateTime.Now;
               Console.WriteLine("vlad's time: {0}", d2 - d1);
            }
        }
    }
}

Проверил. Реально задумывается гораздо чаще.

[pva]

Постановка задачи про рюкзак (bounded knapsack problem) дико напоминает линейное программирование. Или я не прав? (смотрел ссылку, они решили как задачу дискретного оптимального управления)

[ivank]

pva
Честно говоря, не очень представляю как это можно сделать. Все известные мне методы линейного программирования, которые ищут дискретные коэфициенты, в конечном счёте NP-полные (читай: сводятся всё к тому же перебору). Кстати, нашёл описание именно нашего частного случая на википедии: http://en.wikipedia.org/wiki/Subset_sum_problem . Там прямо сказано, что это не задача оптимизации (т.е. линейное программирование не применимо. По крайней мере в чистом виде).

[Vlad Drakula]

ivank
соглашусь что ваш алгоритм для данной задачи (типов наборов чисел) лучьше...(пока я не придумал алгорим быстрее)
но веть и быстрая сортировка имеет шанс работать по n*n, и ничего пользуются...

+ еще одно но:
а как на счет реализации?
если по оптимизировать то можно сократить время работы в 3-7 раз...

[ivank]

Vlad Drakula

но веть и быстрая сортировка имеет шанс работать по n*n, и ничего пользуются...

Я не спорю. Есть сортировка с помощью кучи, которая гарантированно работает за n*logn, но ею не пользуются, т.к. в среднем случае она в несколько раз медленнее быстрой сортировки (которая, кстати называется сортировкой Хоара, на самом деле). Средние случаи встречаются значительно чаще, чтобы перевешивать превосходство хип-сорта над кусортом в худшем случае.

Аналогично в среднем случае твой алгоритм значительно лучше. Вот только на предполагаемых наборах чисел (25-50) вероятность влететь в худший случай максимальна (т.к. чем больше чисел (n>50), тем больше вероятность получить требуемую сумму с помощью твоей эвристики. А при малом n (<25), даже если требуеммую сумму получить нельзя, стоимость полного перебора невелика).

а как на счет реализации? если по оптимизировать то можно сократить время работы в 3-7 раз...

Да это вроде не требуется по условию. Человек готов был ждать по пол-часа и более. И вообще, не умею я оптимизировать на "не-алгоритмеческом" уровне, доверяю компилятору.