powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Перебор вариантов сумм
27 сообщений из 27, показаны все 2 страниц
Перебор вариантов сумм
    #36878460
olegsng
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Добрый день,

столкнулся с такой задачкой - есть некое кол-во чисел (до 200)- нужно перебрать все варианты сумм этих чисел, например есть 800 600 500 400

800+600+500+400
800+500+400
800+600
800+500
800+400
800+600+500
800+600+400
600+500+400
600+500
600+400
500+400
800
600
500
400

чувствую что рекурсия, но как?

Олег
ПС Задачка явно студенческая, да я в другой области работаю, не могу сообразить
...
Рейтинг: 0 / 0
Перебор вариантов сумм
    #36878465
x1ca4064
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
olegsng,

Странная задача: 2^200 это очень много.

А перебор нужно делать без рекурсии - каждае число лбо входит в сумму, либо нет - просто цикл от 0 (все числа не входят) до 2^(кол-во чисел).
...
Рейтинг: 0 / 0
Перебор вариантов сумм
    #36878489
olegsng
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
x1ca4064,

да число большое, но это очень грубая постановка для простоты объяснения, оценки верхнего предела вычислений и получаемых результатов. Поставлю компьютер на просчет и пусть считает, все равно на работе я его не выключаю никогда.

На самом деле числа будут разбиваться на группы, скажем по 50 шт по определенному соотношению "больших" и "маленьких" значений и к ним будет применяться этот же алгоритм 4 раза для 200 (4*50=200) чисел. Если результат в группе подобен всему множеству - то и будем бить на группы.
...
Рейтинг: 0 / 0
Перебор вариантов сумм
    #36878550
Edd.Dragon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
x1ca4064olegsng,
Странная задача: 2^200 это очень много.
А перебор нужно делать без рекурсии - каждае число лбо входит в сумму, либо нет - просто цикл от 0 (все числа не входят) до 2^(кол-во чисел).
Из 200 чисел получится 200 + 199 + ... + 2 + 1 = 20100 сумм, т.е. (N + 1) * N / 2, а не 2^N


olegsng
Если есть числа от 1 до 5, то список всех сумм будет:

1, 1+2, 1+3, 1+4, 1+5,
2, 2+3, 2+4, 2+5,
3, 3+4, 3+5,
4, 4+5,
5

Где ж тут рекурсия?
...
Рейтинг: 0 / 0
Перебор вариантов сумм
    #36878554
Edd.Dragon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
olegsngНа самом деле числа будут разбиваться на группы
Не обязательно, если конечно в этом нет иной необходимости.
...
Рейтинг: 0 / 0
Перебор вариантов сумм
    #36878555
Edd.Dragon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Edd.Dragon
Если есть числа от 1 до 5, то список всех сумм будет:

1, 1+2, 1+3, 1+4, 1+5,
2, 2+3, 2+4, 2+5,
3, 3+4, 3+5,
4, 4+5,
5

Где ж тут рекурсия?
Ой прогнал
Ща )))
...
Рейтинг: 0 / 0
Перебор вариантов сумм
    #36878558
Gatman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
внешний цикл от 0 до 199, внутренний от i до 199, где i - номер итерации первого
во внутреннем цикле числа суммируются от i-го элемента до последнего
на каждой итерации внутреннего цикла получаем новую сумму
на каждой итерации внешнего цикла сумму нужно обнулить
...
Рейтинг: 0 / 0
Перебор вариантов сумм
    #36878599
Edd.Dragon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Количество вариантов: (см. картинку)

Вот как можно разложить рекурсию и перебрать циклами:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
1 - 1+2 - 1+2+3 - 1+2+3+4 - 1+2+3+4+5
|   |     |       |
|   |     |       1+2+3+5
|   |     |
|   |     1+2+4 - 1+2+4+5
|   |     |
|   |     1+2+5
|   |
|   1+3 - 1+3+4 - 1+3+4+5
|   |     |
|   |     1+3+5
|   |
|   1+4 - 1+4+5
|   |
|   1+5
|
2 - 2+3 - 2+3+4 - 2+3+4+5
|   |     |
|   |     2+3+5
|   |
|   2+4 - 2+4+5
|   |
|   2+5
|
3 - 3+4 - 3+4+5
|   |
|   3+5
|
4 - 4+5
|
5            

Ща попробую алгоритм накатать...
...
Рейтинг: 0 / 0
Перебор вариантов сумм
    #36878601
x1ca4064
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Edd.Dragon
Из 200 чисел получится 200 + 199 + ... + 2 + 1 = 20100 сумм, т.е. (N + 1) * N / 2, а не 2^N



Категорически не согласен: начальная постановка "нужно перебрать все варианты сумм этих чисел".
...
Рейтинг: 0 / 0
Перебор вариантов сумм
    #36878602
Edd.Dragon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Правда так вывод будет вперемешку. Лучше по отдельности перебирать сначала все комбинации с 1 слагаемым, потом с 2-мя, потом с 3-мя
...
Рейтинг: 0 / 0
Перебор вариантов сумм
    #36878604
Edd.Dragon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
x1ca4064Edd.Dragon
Из 200 чисел получится 200 + 199 + ... + 2 + 1 = 20100 сумм, т.е. (N + 1) * N / 2, а не 2^N



Категорически не согласен: начальная постановка "нужно перебрать все варианты сумм этих чисел".
Уже поправился ))
...
Рейтинг: 0 / 0
Перебор вариантов сумм
    #36878606
Фотография eNose
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
[не активирован]
[не одобрен]
600+200 = 500+300

причем это будет фигурировать много где.
...
Рейтинг: 0 / 0
Перебор вариантов сумм
    #36878614
olegsng
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Edd.DragonПравда так вывод будет вперемешку.

Это не важно."Нужная" сумма определяется и фиксируется "нужная" комбинация
...
Рейтинг: 0 / 0
Перебор вариантов сумм
    #36878645
avb1003
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Edd.DragonКоличество вариантов: (см. картинку)

Вот как можно разложить рекурсию и перебрать циклами:

Код: plaintext
1.
2.
3.
4.
5.
6.
1 - 1+2 - 1+2+3 - 1+2+3+4 - 1+2+3+4+5
....
|
4 - 4+5
|
5            

Ща попробую алгоритм накатать...
...
Рейтинг: 0 / 0
Перебор вариантов сумм
    #36878661
Памас
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
искомые суммы можно представить как

где,
- числа из множества исходного набора чисел ( ),

- количество чисел во множестве

тогда выражение(строку)
можно рассматривать как представление разрядного 2-ич. числа.
значит, количество " все варианты сумм этих чисел " равно (исключая 0)

при не выполнении условия ( ) потребуется некоторая модификация...
...
Рейтинг: 0 / 0
Перебор вариантов сумм
    #36878662
olegsng
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
avb1003Edd.DragonКоличество вариантов: (см. картинку)


Правильно, для 4-х чисел 15 вариантов, в постановке задачи оно так и показано


Ща попробую алгоритм накатать...
...
Рейтинг: 0 / 0
Перебор вариантов сумм
    #36878664
Памас
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
"x1ca4064" прав
...
Рейтинг: 0 / 0
Перебор вариантов сумм
    #36878835
Edd.Dragon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Сорри, пришлось отвлечься

С циклами сломал себе мозг.
Выше схемка, которую приводил - это как раз под рекурсию:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
#include <iostream>
#include <iomanip>
#include <fstream>
#include <ctime>

using namespace std;

const int n =  20 ;
const int nums[n] = { 1 ,  2 ,  3 ,  4 ,  5 ,  6 ,  7 ,  8 ,  9 ,  10 ,  1 ,  2 ,  3 ,  4 ,  5 ,  6 ,  7 ,  8 ,  9 ,  10 };

int count =  0 ;
ofstream outfile("output.txt", ios::out | ios::trunc);

void stepIn(int pos, int sum)
{
	for(int i = pos; i < n; i++)
	{
		int new_sum = sum + nums[i];
		outfile << setw( 10 ) << new_sum;
		count++;
		if(i < n -  1 ) stepIn(i +  1 , new_sum);
	}
}

int main()
{
	time_t timestamp;
	time(&timestamp);
	outfile << "Started at " << ctime(&timestamp) << endl;

	stepIn( 0 ,  0 );

	timestamp = time(NULL) - timestamp;
	outfile << endl << endl << "Total combinations: " << count << endl;
	outfile << "Process duration: " << timestamp << " sec" << endl;

	return  0 ;
}

Кстати, обнаружил, что вывод endl в поток сильно тормозит процесс. При просчете комбинаций из 20 чисел, если записывать их в столбик по одному, т.е.
Код: plaintext
outfile << new_sum << endl;
а не как выше все в одну строку, то программа работает в 8 раз дольше ))


avb1003
Ага, пока тестил, заметил эти магические числа :(

Так что,
olegsngНа самом деле числа будут разбиваться на группы, скажем по 50 шт
не вариант.

При 20 числах получаем 1 миллион вариантов. Если держать их в оперативке, то на такой массив потребуется 4 Мб памяти, в файле как у меня (по 10 знакомест на 1 число) - 10 Мб файл.

При 30 числах - в 1024 раза больше требования: 4 Гб в оперативке (32-битная винда уже не выдаст приложению столько) или 10 Гб на винт.

При 40 числах - еще в 1024 больше: 4 Тб в оперативке или 10 Тб на винт.

При 50 - еще в 1024 раза больше...
...
Рейтинг: 0 / 0
Перебор вариантов сумм
    #36878836
Edd.Dragon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
* Переменная count в программе - для проверки, так то считать кол-во не надо - известно заранее.
...
Рейтинг: 0 / 0
Перебор вариантов сумм
    #36879302
olegsng
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Edd.Dragon

void stepIn(int pos, int sum)
{
for(int i = pos; i < n; i++)
{
int new_sum = sum + nums[i];
outfile << setw(10) << new_sum;
count++;
if(i < n - 1) stepIn(i + 1, new_sum);
}
}


Ага, похоже

function SearchProfile(Data: PProfileArray; FromIndex, ProfileLen...): Integer;
var
...
begin

for i := FromIndex to Data^.Size-1 do begin
Yield;
M := SearchProfile(Data, i+1, ProfileLen-Data^.Values[i].ProfPartLen, ProfileNumber);

if M = нужное то ......

end;

SearchProfile := ....;
end;

При 80 числах - я не дождался результата, при 40 реальных данных - 5-20 сек на моем стареньком Core2 первого выпуска. Сильно зависит сколько "маленьких" чисел, результат определяется как остаток (ProfileLen-Data^.Values[i].ProfPartLen) от некоего начального значения, если числа "маленькие", то их "больше" в начальном значении.

Результат - отличный при 40, так что 200 буду бить на 5 интервалов.
...
Рейтинг: 0 / 0
Перебор вариантов сумм
    #36879328
Edd.Dragon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Раз вам хранить все варианты сразу не нужно, то конечно проще. Можно варьировать.

авторПри 80 числах - я не дождался результата, при 40 реальных данных - 5-20 сек

Ну вот для 50-ти было бы порядка 5-20 тыс. сек
Для 60 - 5-20 млн. сек. (~ пол года)
Для 70 - 5-20 млрд. сек.
Для 80 - 5-20 триллионов сек (пол миллиона лет)
...
Рейтинг: 0 / 0
Перебор вариантов сумм
    #36879373
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
x1ca4064А перебор нужно делать без рекурсии - каждае число лбо входит в сумму, либо нет - просто цикл от 0 (все числа не входят) до 2^(кол-во чисел).
+1
...
Рейтинг: 0 / 0
Перебор вариантов сумм
    #36879380
olegsng
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Edd.Dragon
Для 80 - 5-20 триллионов сек (пол миллиона лет)

Да уж, мужики бы не дождались, 80 чисел - это 40 изделий в производство, задание на полдня.
Работа не бей лежачего - полдня один раз в полмиллиона лет.

Впрочем, как говорил мой один знакомый - если разработанный нами алгоритм не тянет компьютер, то мы купим новый соответствующий компьютер.
...
Рейтинг: 0 / 0
Перебор вариантов сумм
    #36879385
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
olegsng

Впрочем, как говорил мой один знакомый - если разработанный нами алгоритм не тянет компьютер, то мы купим новый соответствующий компьютер.

а компьютеры он из Топ500 выбирает?
...
Рейтинг: 0 / 0
Перебор вариантов сумм
    #36879431
olegsng
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
ZyK_BotaN

а компьютеры он из Топ500 выбирает?

думаю, что какой нибудь современный бытовой граф акселератор с массово параллельными процессорами (сколько их там сейчас в АТИ - 1000 потоковых процессоров?) такую задачку расщелкает быстро
...
Рейтинг: 0 / 0
Перебор вариантов сумм
    #36879448
Edd.Dragon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
olegsng,
В миллиард раз? ))
Нет. Вот лет через 20 - может быть, а пока...

Кстати, вы в своем алгоритме кол-во перебранных вариантов для проверки не считали? У меня 30 чисел (все от 1 до 10) перебирает без печати в файл и каких-либо других проверок, просто перебор, на старом одноядернике - 8.5 сек. 31 число - как и предполагается - 17 сек.

А у вас 40 за такое же время. Не может же двуядерник быть в 500 - 1000 раз быстрее быть. Может не все перебирается?
...
Рейтинг: 0 / 0
Перебор вариантов сумм
    #36879480
olegsng
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Edd.Dragon

Кстати, вы в своем алгоритме кол-во перебранных вариантов для проверки не считали? У меня 30 чисел (все от 1 до 10) перебирает без печати в файл и каких-либо других проверок, просто перебор, на старом одноядернике - 8.5 сек. 31 число - как и предполагается - 17 сек.

А у вас 40 за такое же время. Не может же двуядерник быть в 500 - 1000 раз быстрее быть. Может не все перебирается?

Варианты не считал, но у меня задача имеет ограничение, сначала заведомо неправильные варианты отбрасываются, меня интересует не сама сумма, а остаток между суммой и некой константой, плюс "хорошие" суммы, а точнее их компоненты - из рассмотрения убираются, т.е. как только я решил, что 500+300 - это то, что нужно - эти числа убираются, соответственно уже не 40 чисел а 38.
...
Рейтинг: 0 / 0
27 сообщений из 27, показаны все 2 страниц
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Перебор вариантов сумм
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]