Переборные задачи Опции

[Сергг]

Здравствуйте!
Кто-нибудь объясните как происходит перебор вариянтов в след. задаче: есть кучка камне(20) нужно раскидать их на две кучки наиболее близкого веса. Может кто подскажет, Алгоритм как это делать.

[trminator]

Каждый камень можно положить или в первую кучку, или во вторую (третьего не дано). Тогда заведем такой массив А(его еще называют характеристический вектор):
A[i]=0, если i-й камень в 1-й кучке,
A[i]=1, если i-й камень во 2-й кучке.

Осталось только построить все возможные такие векторы, и посмотреть, в каком случае разница будет минимальной.

Пример всех массивов для трех камней:

Код

0 0 0 (все камни в 1-й кучке)
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1 (все камни во 2-й кучке)

Кстати, можно заметить, что это - двоичные представления чисел от нуля до 2^3 - 1= 8. То есть чтобы сгенерировать такие массивы, можно брать числа от 0 до 2^20 - 1 (то есть до 1 048 575) и раскладывать в двоичную систему счисления

Варианты с сортировками ИМХО не проходят. Я так уже обломался один раз (можно даже вспомнить топик в этом разделе, там такая же задача примерно была)