Всем Утро/День/Вечер
У меня есть массив 1 2 3 4
Надо перебрать все возможные суммы элементов (или составить очереди обхода)
Тобишь для массива 1 2 3 4 это
1+2+3+4
1+2
1+2+3
1+2+4
1+3
1+3+4
1+4
2+3
2+3+4
2+4
3+4

Бьюсь второй третий день рекурсиями никак невыходит((
ЗЫ решаю задачку acm.timus.ru/problem.aspx...

hardcoder Сообщение 22/03/2012 08:56 Копия темы
Не парьтесь. Вы не в том классе.

Ту задачку, которую ВЫ описали – решить легко:
двоичный счет – если в первом бите единичка – прибавляем первое слагаемое, если нолик – не прибавляем.
Если во втором – второе слагаемое и т.п.

то есть получаем:
0001
0010
0011
0100
0101
и т.п.

Это и будет ответом на вопрос – "Надо перебрать все возможные суммы элементов"

А вот задача, на которую вы ссылаетесь – гораздо сложнее. :)
Гуглить "задача о ранце" или "задача о контейнерах".

kermit32dll Сообщение 22/03/2012 09:04 Копия темы
Пришло в голову за 5 минут размышлений:

1. Берём целочисленный тип данных, у которого побольше битов, и создаём переменную этого типа, которая у нас будет маской
2. Пишем в неё еденицу (1)
3. Берём массив, который дан в условии задачи
4. Делаем цикл:

4.1. переводим маску в двоичный код
4.2. если в маске после конвертации только одна еденица – пропускаем цикл (взят только 1 элемент массива не с чем суммировать)
4.3. если в маске несколько едениц – берём элементы, на которые указывает маска, и плюсуем их к общей сумме элементов.
4.4 прибавляем к маске 1.
4.5 повторяем цикл

А иначе тут без хитронавёрутых циклов не обойтись.

kermit32dll Сообщение 22/03/2012 09:16 Копия темы
Посмею возразить, метод решения задачи, на которую автор поста привёл ссылку, весьма схож с описанным. Разве что полную сумму всех возможных комбинаций элементов массива искать не надо, а только перебирать комбинации сумм в поиске тех, что совпадают с числом в первой строчке, и запоминать при этом номера элементов.

woofer46 Сообщение 22/03/2012 09:24 Копия темы

hardcoder Сообщение 22/03/2012 09:24 Копия темы
Метод решения типа "перебрать все суммы", естественно работает. Теоретически...
Только нужно немножко понять, что для 50 карт, например, комбинаций будет чуть больше миллиона миллиардов (не знаю как такое число называется :) ) Не говоря уже про сто карт (тысяча миллиардов миллиардов миллиардов :))) ).
Поэтому перебором решать эту задачу – это полный бред.

Если автор даже затрудняется перебрать все возможные суммы,
то очевидно, что задачка "немножко" не подходит ему по уровню...

woofer46 Сообщение 22/03/2012 09:25 Копия темы
Придется повышать уровень, чтож поделать

hardcoder Сообщение 22/03/2012 09:26 Копия темы
Конечно. Это дело полезное и наживное.

Секрет в том, чтобы как можно сильнее ограничить перебор со всех возможных сторон.
ну например, навскидку
- если сумма трех элементов уже превышает вес колоды, то, очевидно, пробовать прибавлять четвертый глупо.
- если вес колоды нечетный, то глупо складывать карты с четными весами.
И т. д. и т. п.

Задача в том и состоит, чтобы максимально избавиться от перебора, а не пилить "в лоб".

kermit32dll Сообщение 22/03/2012 09:27 Копия темы
Уже готовые функции есть, не знаю, на каком языке Вы программируете, везде они по-разному называются.

woofer46 Сообщение 22/03/2012 09:30 Копия темы
Да, вроде уже нагуглил

kermit32dll Сообщение 22/03/2012 09:33 Копия темы
Для 50 карт комбинаций будет 1125 триллионов (1.125 * 10^15). Но ведь в условии задачи не говорится, что метод должен решать любое количество карт за 1 секунду. И тем более все варианты потребуется перебирать только если у задачи нет решения, а если оно есть, перебор закончится гораздо быстрее.

woofer46 Сообщение 22/03/2012 09:36 Копия темы
ограничение по времени пол секунды, а максимум карт 100 ))

DrSun Сообщение 22/03/2012 10:10 Копия темы
Что такое "еденица"? Что-то с едой связано?

kermit32dll Сообщение 22/03/2012 10:11 Копия темы
Можно алгоритм оптимизировать, скажем, делать перебор только до тех пор, пока первая карта в комбинации не будет весить больше, чем "неполная" колода целиком. Возможностей много, просто непонятно, на каком оборудовании требуется достичь результата в пол-секунды, в 2003м году процессоры были раз в 20 слабее. У можь у них там стоит какой-нить задрипаный пентиум 3, а у меня шестядерный Core 7 Extreme.

kermit32dll Сообщение 22/03/2012 10:14 Копия темы
Всегда забавляло, когда обсуждаются серьёзные темы, обязательно найдётся умник, который докопается не к сути проблемы, обсуждаемой в топике, а к случаянно допущенной орфографической ошибке.

DrSun Сообщение 22/03/2012 10:16 Копия темы
Всегда забавляло, когда тридцатилетняя невежда, вместо того, чтобы покраснеть как рак, еще и возникает :)) случайно один раз пишут, а не десять.

kermit32dll Сообщение 22/03/2012 10:29 Копия темы
Слово заклинило в таком написании, хотя я прекрасно знаю, как оно пишется грамотно. А вот докапываться до правописания, когда топик совсем о посторонних вещах – это печально. Обычно так делают, когда совершенно не смыслят по делу, но докопаться хочется.

kermit32dll Сообщение 22/03/2012 10:30 Копия темы
А почему не написал автору поста, что он пишет слова в начале предложения с маленькой буквы, не ставит точки, и использует англицизмы типа "нагуглил", которые вообще в русском языке отсутствуют?

RiDDi Сообщение 22/03/2012 12:24 Копия темы
Так уж о посторонних. "Орфографическая" ошибка в коде может привести хорошо если к прекращению работы программы, а то и к неправильной работе, лагам. Это тренируется с детства – один неверный символ в чате онлайн игры и Ваш пароль уйдет в массы ))

Как можно допустить подобные ошибки в 30 лет действительно не понятно. И это не случайность и не описка, Вы действительно не знали как пишется это слово. Кроме того Вы не учитесь, не принимаете рациональную критику, – Вы выпендриваетесь и сливаетесь куда-то в пунктуацию, общее оформление текста и т.д. Пунктуация зависит от абстрактного мышления, оформление – от личных вкусов и предпочтений. Орфография зависит напрямую от синхронности работы мышления и познания. Люди думают словами, если Вы не замечали. Вы что, думаете "едЕница" что-ли? )) Явно ведь думаете "единица", но почему-то делаете в частности пишите не так. Это очень нехороший симптом, Роман прав.

hardcoder Сообщение 22/03/2012 12:46 Копия темы
Естественно, задача поставлена так, чтобы тупое решение не пролазило...

Даже если вы за один такт проца считаете и проверяете одну сумму (неважно из 50 элементов или из одного), и проц у вас работает на частоте 10 гигагерц и процов у вас в компе десять, то на полный перебор колоды из 50 карт уйдет 10000 секунд – это почти три часа.
 
А тупой перебор колоды в сто карт сильно напряжет и гугловский датацентр вместе с натовскими суперкомпьютерами... :)

Ну очевидно же!

kermit32dll Сообщение 22/03/2012 12:50 Копия темы
Решение можно и нужно оптимизировать, но решать олимпиадную задачу по информатике я врядли буду прямо тут. Человек хотел решение, он его получил, а оптимизация – это уже трудоёмкий процесс, которым на форуме ну никак заниматься не хочется ;)

kermit32dll Сообщение 22/03/2012 12:56 Копия темы
Синтаксическую ошибку в коде сразу же отбракует компилятор.

Я, когда пишу, пишу, как думаю, а в голове настолько много всего, что некоторые слова выпадают так, как они звучат, а звучат они иначе, нежели как пишутся. И ошибки допускаются одни и те же, выглядит как незнание, а на самом деле так мозг настроился. Я когда пишу код, могу десять раз вместо "else" написать "esle", причём не заметить этого, и сделать это только потому, что в мозгу что-то заклинило, а не потому что я не знаю, как это слово пишется. Этот симптом называется "рассеянность". Понятно, что для слова "единица", проверочное слово – "единый", просто так вышло. Но ведь вам же тут обязательно нужно докопаться.

hardcoder Сообщение 22/03/2012 14:12 Копия темы
Я бы не называл этот процесс "оптимизацией".

Можно построить лестницу до луны... Теоретически... наверное... :)
А можно сделать ракету... Ракету довольно сложно назвать "оптимизированной лестницей" :)

kermit32dll Сообщение 22/03/2012 14:35 Копия темы
Оптимизация порой приводит к полной переделке алгоритма. Никто не говорит, что предложенный вариант является единственным правильным, тут ещё работать и работать. Но автору поста это не требуется.

RiDDi Сообщение 22/03/2012 15:01 Копия темы
Господи Боже ))) Сергей, "синтаксические" и "орфографические" это разные ошибки )) 
Синтаксис это определенный порядок в словосочетании.
Орфография это в слове.
В программировании орфографической ошибкой будет, например, ошибка в названии метода. Вместо get например set или git, gat. И если такие методы доступны, никакой компилятор этой ошибки не заметит.
Я же четко написал "орфографические".
Ну как вот так можно?
Если это рассеянность, то крайняя степень при которой легко вместо расчески можно использовать топор )) Вы считаете в этом случаи тоже не надо обращать внимания? )

kermit32dll Сообщение 22/03/2012 15:24 Копия темы
Если накосячить в названии метода, и при этом ещё и так совпадёт, что метод с ошибкой в имени тоже есть, то это скорее всего сразу же вылезет при дебаге. Я считаю, что не надо в теме про программирование обсуждать орфографию, вот и всё. Если кто-то не ту букву написал (кстати, при этом даже не живя в России) – да пожалуйста, какое отношение это имеет к сабжу? А поффтопить можно и в другой теме.