Как разбить массив на два подмассива?

Question

[Андрей Выдрин]

Нужно разбить массив на две части так, что бы сумма элементов была равна. Количество элементов в подмассивах может отличаться. Например: есть массив А={1, 1, 1, 1, 4}. Он должен разбиться на два B={1, 1, 1, 1} и C={4}. Можно, даже лучше будет, без кода, только алгоритм.

Comments

[lexaxaxa]

первый эл.(part1) равен сумме всех остальных?-нет не равен. прибавляем к первому эл. второй и из part2 вычитаем второй эл. Первые два эл.(part1) равны остальным(part2)-и тд

Answer 1

[Виталий Витренко]

Partition problem.
В гугле много информации относительного этого.

Comments

[Андрей Выдрин]

спасибо, не знал как это назвать.

Answer 2

[Spetros]

Перебор и суммирование позиций можно реализовать циклом или рекурсией. Берете первый элемент, сравниваете его с суммой элементов после него, если не совпало - прибавляете к нему второй элемент и сравниваете эту сумму с суммой элементов после второго и т.д. пока суммы не сравняются.

Answer 3

[Dvvarreyn]

Если в данном случае возможно mozgless-решение, то к целочисленной линейной задаче удовлетворения ограничениям можно свести.
Если порядок не важен (то есть не на левую и правую части, а на какие угодно части), то по сути, для заданного
С \in R^n
нужно найти
x \in {0, 1}^n
такой, что
sum_i с_i(2x_i-1) = 0
И дальше подсунуть в какой-нибудь солвер, например, GLPK, COIN-OR CBC или SCIP.

Answer 4

[mamkaololosha]

Самое в лоб за O(N):
1) идем одним итератором справа, другим слева, пока они не столкнутся.
2) если правая часть меньше, то продолжаем движение влево, пока не будут равные суммы или не достигнем начала массива
3) если левая часть меньше, то продолжаем движение вправо, пока не будут равные суммы или достигнем конца массива

Comments

[Андрей Выдрин]

ну такое решение не подходит, т.к. сильно зависит от того в каком порядке идут элементы. Для {1, 4, 1, 1, 1} работать уже не будет

[mamkaololosha]

Андрей Выдрин: естественно, ведь массив 1, 4, 1, 1, 1 нельзя разбить так, чтобы сумма правой части была равна левой.

[Derga]

mamkaololosha, можно {1, 1, 1, 1} и {4}. Как решить такую задачу?