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

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

Кстати, я вспомнил. Это называется задачей об укладке рюкзака (http://en.wikipedia.org/wiki/Knapsack_problem), частный её случай. Это NP-полная задача в общем случае. Её можно решить за "псевдо-полиномиальное" время, что я и делаю. предлагаю просесть всю статью.

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

[Vlad Drakula]

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

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



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