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

[Сергг]

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

[dushik]

1. Создаешь. Два массива по 10 эл. И массив с 20-ю камнями.
2. Вводишь с клавы, или присваеваешь значение каждому камню.
3. Сортируешь массив с камнями...
4. Первые 10 эл. массива с камнями присваеваешь одноу из массиво с 10-эл. Другие 10 - другой половине...
Это мой вариант...

[fms]

хм.. по моему тогда они не будут равными.. если отсортировать камни и присвоить 1-ые 10 1-ому массиву а 2-ые 10 2-ому..

[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) и раскладывать в двоичную систему счисления

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