Полный перебор

[Sergio471]

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

[venco]

Почитайте про задачу о ранце (knapsack problem):
http://ru.wikipedia.org/wiki/%D0%97%D0% ... 1%86%D0%B5

[Sergio471]

Почитал. Но можно как-нибудь без рекурсии здесь обойтись? Да и тяжело проследить аналогию с рюкзаком. Т.е. как перебрать все сочетания элементов массива?

[venco]

Аналогия прямая: по сути Вам надо максимально заполнить рюкзак вместительностью в половину суммарного веса всех камней.

[Zealint]

Если есть сильное ограничение на вес любого из n камней, то эта задача решается методом динамического программирования.

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

Пусть $A_i$ - массив, в котором 1 на месте i означает, что можно получить сумму весов, равную i, и 0 в противном случае. Сначала $A_0=1$, а все остальные элементы равны 0. Пусть вес i-го камня равен $w_i$.
Пусть $N=\sum_i w_i$

Цикл по i для каждого камня
  Цикл по j по всем ячейкам A от (N-w[i]) до 0 ( в обратном порядке! )
    если А[j] = 1 то A[j+w[i]] := 1    

После этого мы знаем, какие веса могут появиться, а какие - не могут.
Теперь, если мы решили, что в одной кучке будет вес i, то в другой будет N-i, значит нам нужно найти такое i, чтобы разница $|i-(N-i)|$ была минимальной. Значит надо найти такое $i$, для которого $A_i=1$ и величина $|2i-N|$ минимальна.

Недостаток: нужно создавать массив, размера N. Зато если N окажется не очень большим, то метод работает существенно быстрее полного перебора. Как потом понять, какие камни в каких кучках будут, тут уже не трудно самому придумать.

[sergey83]

Интересно, а применим ли в принципе в этой задаче принцип динамического программирования, если веса не целые числа, а иррациональные?
Второй вариант, веса берутся из экспериментальных данных. Многие веса отличаются в четвертом знаке после запятой. Из-за этой мелкой пакости таблица динамического программирования будет, как минимум, на 10000 (10 в степени 4) элементов? А если веса отличаются в шестом знаке, то таблица будет на миллион (10 в степени 6) элементов?

[Zealint]

Цитата:

Интересно, а применим ли в принципе в этой задаче принцип динамического программирования, если веса не целые числа, а иррациональные?

Принцип динамического программирования (в самом широком смысле) применим к любой задаче. Только сам метод будет другим. Именно предложенный метод, конечно, не будет работать. Но если иррациональные числа "далеки" друг от друга, то их можно заменить на рациональные.

Цитата:

Второй вариант, веса берутся из экспериментальных данных. Многие веса отличаются в четвертом знаке после запятой. Из-за этой мелкой пакости таблица динамического программирования будет, как минимум, на 10000 (10 в степени 4) элементов? А если веса отличаются в шестом знаке, то таблица будет на миллион (10 в степени 6) элементов?

Битовое поле на $10^6$ бит будет занимать всего 123 Кб. Многократная беготня по такому полю - не слишком сложная задача. Даже не задача. Да, я согласен, что если брать пару сотен миллиардов, то метод становится немного неудобным. Значит надо придумывать другой.

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