Поиск элементов массива, чья сумма равна заданному числу

ivank · Отправлено: **17:01, 14-09-2006** | #11

Qwe1
Ладно. Рассмотрим всё по порядку. Пусть у нас есть m целых положительных элементов a[i] и трубеится найти можно ли из них составить сумму равную n. Создадим массив can[i][k] размера m на n+1. can[i][k] = 1, если мы можем получить каким-то образом суммируя только элементы a[0]...a[i] сумму равную k. Нас интерисует значение can[m][n], т.е. можем ли мы получить используя элементы a[0]...a[m] сумму n.

Очевидно can[0][k] = 0, для всех k != a[0] и k != 0. can[0][0] = 1 и can[0][a[0]] = 1. Т.е. используя один элемент мы можем получить только сумму равную 0 или этому элементу.

Рассмотрим как по массиву can[i-1] можно построить can[i]. Очевидно, что используя i элементов всегда можно получить те же суммы, что и используя i=1 элемент (просто не добавляя к прежним суммам i-й элемент). Т.е. если can[i-1][k]=1, то can[i][k]=1 так же. Кроме того, к любой из прежних сумм мы можем добавить i-й элемент, т.е. если can[i-1][k]=1, то can[i][k+a[i]]=1 так же. Во всех остальных случаях can[i][k]=0.

Реализация вышеописанного в (псевдо)коде будет выглядеть вот так:

Код:

int can[m][max_sum+1], i, j;
for (i = 0; i < m; ++i)
    for (j = 0; j <= max_sum; ++j)
        can[i][j] = 0;
can[0][0] = can[0][a[0]] = 1;
for (i = 1; i < m; ++i)
{
    for (j = 0; j < max_sum; ++j)
        can[i][j] = can[i-1][j];
    for (j = 0; j < max_sum; ++j)
        if (can[i-1][j])
            can[i][j+a[j]] = 1;
}

Пользуясь тем фактом, что у нас в can[i] по сравнению с can[i-1] только дописываются единички, а так же тем, что все элементы мы можем модифицировать массив прям на месте, вместо того, что бы иметь цепочку массивов can[0]...can[m].

Вот так:

Код:

int can[max_sum], i, j;
for (i = 0; i <= max_sum; ++i)
    can[i] = 0;
can[0] = 1;
for (i = 0; i < m; ++i)
    for (j = max_sum; j > 0; --j)
        if (j >= a[i] && can[j-a[i]])
            can[j] = 1;

В результате can[n] = 1, если можно получить сумму равную n.

Теперь, если вместо 1 в can[k] ставить то, число которое мы добавили для получения суммы k, то можно будет получить список всех чисел, которые необходимо было просуммировать.
b1 = can[k] - первое число
b2 = can[k-b1] - второе число
b3 = can[k-b1-b2] - третье число
b4 = can[k-b1-b2-b3] - четвёртое число.
итд

В коде это будет так:

Код:

printf("Всё хорошо, путь:\n");
for (i = n; i != 0; i -= way[i])
    printf("%d\n", way[i]);

Vlad Drakula · Конфигурация компьютера

ivank
чего то ваш алгоритм есть слишком много памяти...
мне вот кажется что придумать алгоритм который есть в max_sum+1 раз меньше памяти не так и сложно...
чтобы не быть голословным скоро приведу пример...

Vlad Drakula · Конфигурация компьютера

код на C# котонрый выводит все элементы...

PHP код:


using System;



namespace summ

{

    class Class1

    {

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

                }

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

                {

                    s[p + 1] = i;

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

                }

            }

        }



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

        {

            int[] s = new int[l];

            su(m, s, 0, -1, l, size, 0);            

        }



        static void Main(string[] args)

        {

            int l = 1000;

            int[] m = new int[l];



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

            {

                m[j] = j;

            }



            summ(m,l, 10);

        }

    }

}

ivank · Отправлено: **02:59, 24-09-2006** | #14

Vlad Drakula
Ты просто рекурсивно перебираешь все возможные суммы. Выше уже давалась оценка их количества. Если коротко: афигеть как много. Твой код будет мягко говоря очень долго думать в любом сколь-нибудь сложном случае (время его работы в худшем случае - 2^n, где n - число чисел). Мой гарантированно закончится за O(m*n), где n - число чисел, m - требуемая сумма (максимальная нас не интересует, тут я немножко слажал в описании выше.) Памяти потребуется m. Да, это много. Но это разумная плата за полиномиальное время работы алгоритма вместо экспоненциального.

Сейчас mono соберу и приведу тест, на котором твой код сильно задумается.

ivank · Отправлено: **03:41, 24-09-2006** | #15

Скачал моно. Прогнал простейший тест.

Итак, сначала моя программа в первый раз доведённая до работающего состояния (читай: в первый раз скормил компилятору и поправил очевидные очепятки).

Код:

#include <stdio.h>

int main()
{
/*
	// тест, приведённый оригинальным автором поста
	int num[] = {
		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
		};
	const int n = sizeof(num)/sizeof(int);
	const int m = 350000;
*/
	// мой тест, вешает программу Влада
	const int n = 1000; // количество чисел в наборе
	int num[n]; // сами числа. Втупую подряд
	for (int i = 0; i < n; ++i)
		num[i] = 1+i;
	const int m = n*(n+1)/2-1; // сумма всех чисел, кроме первого

	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])
	    printf("Всё плохо\n");
	else
	{
	    printf("Всё хорошо, путь:\n");
	    for (int i = m; i != 0; i -= way[i])
	        printf("%d\n", way[i]);
	}

	delete[] way;
	return 0;
}

Отрабатывает за секунду в случае "сложного" теста. Мгновенно на примере приведённом автором вопроса.

Программа влада с тем же синтетическим тестом. Не заканчивается никогда.

Код:

using System;

namespace summ
{
    class Class1
    {
        static void 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);
                }
                else if(corsize + m[i] < size)
                {
                    s[p + 1] = i;
                    su(m, s, i + 1, p + 1, l, size, corsize + m[i]);
                }
            }
        }

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

        static void Main(string[] args)
        {
            int l = 1000;
            int[] m = new int[l];

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

            summ(m,l, l*(l+1)/2-1);
        }
    }
}

Vlad Drakula · Конфигурация компьютера

ivank

Цитата:

Выше уже давалась оценка их количества.

1) тыкни носом в отценку.
2) дненм проведу этот тест и посмотнрю на результат.

ivank · Отправлено: **13:43, 24-09-2006** | #17

Цитата:

P.S. В предыдущем посте я наврал. На самом деле при "лобовом подходе" перебирать надо даже SUM(k=1, n, C_n_k). Т.е. сумма всех цэ из эн по ка для всех ка от 1 до эн. Это ещё хуже.

Честно говоря, я склоняюсь к мысли, что эта сумма будет равна 2^n. Поскольку бинарных наборов длины n может быть всего 2^n. А каждый бинарный набор характеризует собой какую-то уникальную сумму (комбинацию чисел). Перебрать их, если делать втупую, надо все. В общем, чистая экспонента.

P.S. Только что проверил эту мысль на бумажке. Действительно, SUM(k=1, n, C_n_k) = 2^n.

Vlad Drakula · Конфигурация компьютера

ivank

PHP код:


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 summ(int[] m, int l, int size)

        {

            int[] s = new int[l];

            su(m, s, 0, -1, l, size, 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;



            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 = 500;

            int[] m = new int[l];



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

            {

                m[j] = l - j;

            }



            d1 = DateTime.Now;                

            summ(m,l, l*(l+1)/2-1);

            d2 = DateTime.Now;

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



            d1 = DateTime.Now;                

            summ2(m,l, l*(l+1)/2-1);

            d2 = DateTime.Now;

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

        }

    }

}

чтож... поставим прогмаммы в равные словия по функциональности...

int l = 500;
eval time: 00:00:00.0200288
eval time: 00:00:00.5708208
int l = 700;
eval time: 00:00:00.0300432
eval time: 00:00:03.7754288

разница в времени работы не в вашу пользу...

ivank · Отправлено: **15:47, 24-09-2006** | #19

Vlad Drakula
Влад. Давай не будем подгонять входные данные. Вернее, моей программе всё равно, подгоняй их или нет. Время работы зависит только от требуемой суммы и числа элементов. Для твоей программы имеет значение то, в какой последовательности заданы элементы и какую сумму мы ищем. При определённых входных данных она подвисает, что я продемонстрировал. Понятно, что в том случае, когда первый же перебор заканчивается успешно твоя программа отработает мгновенно. Но это _подгон_.

Давай посмотрим как ты изменил мой тест:

Код:

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

            d1 = DateTime.Now;                
            summ(m,l, l*(l+1)/2-1);
            d2 = DateTime.Now;
            Console.WriteLine("eval time: {0}", d2 - d1);

Теперь l*(l+1)/2-1 - это не сумма всех чисел кроме первого. Это сумма всех чисел, кроме последнего. При твоём порядке перебора это будет вторая возможность рассмотренная твоей программой.

Приведу генератор теста, на котором твоя программа будет виснуть всегда. Мы просто ищем сумму всех элементов, кроме элементов равных минимальному. Причём один из минимальных элементов мы кладём в середину массива. Можешь заполнять исходный массив как хочешь - программа будет думать долго всегда. Тест синтетический, но он показывает, что твой алгоритм в худшем случае не работает, и что время моего не зависит от входных данных (вернее, зависит только от m и n, но не самих суммируемых чисел).

Можешь попробовать заполнять m как хочешь. Увидишь, что твой код по прежнему очень долго думает.

Вот код. Я немного его модифицировал. В частности убрал вывод на консоль, чтобы не мешал на время смотреть. А так же сделал "свою" функцию зависимой от третьего параметра. Кроме того, поменял местами вызовы своей функции и твоей. Т.к. твоя подвисает -> до выполнения моей никогда дело не дохдит, если твоя первая.

Код:

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 summ(int[] m, int l, int size)
        {
            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 = 500;
            int[] m = new int[l];

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

            // Старый тест
            d1 = DateTime.Now;                
            summ2(m, l, l*(l+1)/2-1);
            d2 = DateTime.Now;
            Console.WriteLine("ivank's eval time: {0}", d2 - d1);

            d1 = DateTime.Now;                
            summ(m, l, l*(l+1)/2-1);
            d2 = DateTime.Now;
            Console.WriteLine("vlad's eval time: {0}", d2 - d1);

            // Новый тест
            // Требуется сумма всех элементов, кроме элемента из середины массива
            // Поиск минимального элемента и перестановка его в середину массива
            int min = 0;
            for (int j = 0; j < l; ++j)
                if (m[j] < m[min])
                    min = j;
            int temp = m[min];
            m[min] = m[l/2];
            m[l/2] = temp;

            // Нужна сумма всех элементов за исключением равных минимальному
            int needed = 0;
            for (int j = 0; j < l; ++j)
                if (m[j] != m[l/2])
                    needed += m[j];

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

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

       }
    }
}

(ушёл, буду в восемь)

Vlad Drakula · Конфигурация компьютера

ivank

PHP код:


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

        {

            int m = n*(n+1)/2-1; // сумма всех чисел, кроме первого



            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 = 800;

            int[] m = new int[l];



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

            {

                m[j] = l - j;

            }



            // Новый тест

            // Требуется сумма всех элементов, кроме элемента из середины массива

            // Поиск минимального элемента и перестановка его в середину массива

            int min = 0;

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

                if (m[j] < m[min])

                    min = j;

            int temp = m[min];

            m[min] = m[l/2];

            m[l/2] = temp;



            // Нужна сумма всех элементов за исключением равных минимальному

            int needed = 0;

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

                if (m[j] != m[l/2])

                    needed += m[j];





            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:03.7854432
vlad's time: 00:00:00.0300432

еще раз придумаешь новый тест?