Задача на паскале: Разделить элементы массива на 2 группы так, что бы разность между ними была минимальна.

[Rhc]

Всем привет! Помогите оформить или подсказать код к вот такой задаче:

1. Вводится число, означающее количество элементов массива.
2. Разделить элементы массива на 2 группы так, что бы разность между ними была минимальна.
Например, вводим:
3
1 3 5
Получаем:
1
Или ещё
4
1 1 1 1
Получаем:
0

Как я решил эту задачу:
(Допустим, входные данные были:
3
1 3 5)
1. Ищем сумму и делим на два (1+3+5)/2=4,5.
2. Нужен массив, длина которого будет в 2 раза меньше, чем длина введённого.
2.1. Если длина массива нечётная, то округлить длину массива в меньшую сторону.
3. "Засовываем" все возможные комбинации чисел в наш обрезанный массив и искать разность чисел с тем, что получилось в п. 1.
3.1. Разность брать по модулю, чтобы не было геморроя.
4. Наименьшая возможная разность и будет решением, но не будет ответом, так как ответом будет эта минимальная разность умноженная на два.

Как теперь всё это оформить в виде кода?

[DpolenST]

по-моему вы не верно понимаете условия задачи

2. Разделить элементы массива на 2 группы так, что бы разность между ними была минимальна.

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

Вот только не понятно какая разность имеется ввиду?
а) разность суммы элементов в группах
или
б) разность между количеством элементов в группах

[Rhc]

Сообщение от DpolenST

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

Вот только не понятно какая разность имеется ввиду?
а) разность суммы элементов в группах
или
б) разность между количеством элементов в группах

а)

Т.е. a[1]:=1 a[2]:=3 a[3]:=5 а сумма будет 9
У меня там не условие идёт, а моё решение . Там же ниже написал, что
потом я беру массив (в теории: кода нет), который в два раза меньше входного и округляю его в нечётную
сторону (чтобы памяти меньше использовалось).

[DpolenST]

1. Сортировать элементы основного массива по убыванию
2. Найти минимальную разность двух массивов
Основная идея поиска состоит в том, что берется максимальный элемент (после сортировки он у нас на "0" месте) в первый массив, второй во второй, находится разница сумм элементов, если разница больше нуля, то есть во втором массиве элемент меньше чем в первом, то во второй массив добавляется еще один элемент, если же разность снова положительная значит во второй массив добавляется еще один элемент и так далее пока разность не будет отрицательна, это как раз и значит, что во втором массиве сумма элементов превысила сумму элементов первого массива, значит следующий элемент нужно добавить в первый массив

Это не совсем полноценный вариант, но хотя бы направление в какую сторону двигаться)

[Serge_Bliznykov]

Оптимальный ответ даст только ПОЛНЫЙ перебор. При количестве предметов (очень примерно) больше 30 это уже не реально (банально время перебора превышает все мыслимые допустимые ожидания).
Но есть алгоритмы, которые достаточно быстро дают решение БЛИЗКОЕ к оптимальному.
Вот, сходите по ссылочке - ТЫРК

[Rhc]

Сообщение от Serge_Bliznykov

Оптимальный ответ даст только ПОЛНЫЙ перебор. При количестве предметов (очень примерно) больше 30 это уже не реально (банально время перебора превышает все мыслимые допустимые ожидания).
Но есть алгоритмы, которые достаточно быстро дают решение БЛИЗКОЕ к оптимальному.
Вот, сходите по ссылочке - ТЫРК

Навскидку, сколько моим способом будут обрабатываться 100 элементов?
Я так понимаю, этот алгоритм работает примерно так:
Вводим
4
2 1 19 18

Программа будет работать так:
Берутся 19 и 18
К 19 идёт 1 а к 18 идёт 2.
Разница между ними будет 0.
Это я понял, но как реализовать?
Результат нужен точный, а не приближённый.

[Аватар]

Результат нужен точный, а не приближённый

Про точный результат вам уже сказали - только полный перебор всех возможных вариантов разбивки. Всеми остальными способами этот наиболее оптимальный вариант можно получить только случайным образом

[Rhc]

Сообщение от Аватар

Про точный результат вам уже сказали - только полный перебор всех возможных вариантов разбивки. Всеми остальными способами этот наиболее оптимальный вариант можно получить только случайным образом

Хорошо, как будто выглядеть код для полного перебора?)
По предложенной здесь идеи я сделал программу, но она
вообще ни разу правильный ответ не выдала. Точнее, она
может выдать правильный ответ, но только в частных случаях.

[Poma][a]

По предложенной здесь идеи я сделал программу

Дык покажите её..

[Аватар]

Хорошо, как будто выглядеть код для полного перебора?

Количество способов разбивки С(1,n)+C(2,n)+..+C(n mod 2,n). Если и ошибся, то думаю не кардинально. Здесь C(i,n)=n!/((n-i)!*i!). А теперь представте 100 предметов и C(50,100)=100!/(50!*50!). 100! это число примерно со 158 цифрами. Сколько лет потребуется компьютеру для расчета всех способов разбивки? (или вернее миллионов лет)