Можно ли разложить гантели в кучки равной массы и с равным количеством гантелей

[fourston]

Есть N гантелей массой m1..mN. Определить можно ли разложить гантели в кучки равной массы и с равным количеством гантелей. Использовать динамический массив.

Я предполагаю, что надо найти всю сумму и разделить ее на 2, так мы найдем какой массы будут кучки. Затем найти все возможные варианты наборов гантелей этой суммы и, если найдутся кучки с равным количеством гантелей, вывести "да, возможно"

[Serge_Bliznykov]

а с чего Вы решили, что делить нужно на два?!
имхо, кучек может быть две или больше

[fourston]

кучки должно быть две.

[Serge_Bliznykov]

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

кучки должно быть две.

Я не то, чтобы хотел с ваши дисскутировать, но я прошу Вас уточнить:
из чего это следует?

В задании я этого не увидел.


кстати, формально говоря, в задании ещё не сказано, что ВСЕ гантели должны быть разложены по кучками. Впрочем, тут я соглашусь, что это явно подразумевается...


p.s. и ещё хочу предостеречь/проинформировать: ваша задачка совсем на так проста, как она кажется на первый взгляд!

[fourston]

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

Я не то, чтобы хотел с ваши дисскутировать, но я прошу Вас уточнить:
из чего это следует?

В задании я этого не увидел.


кстати, формально говоря, в задании ещё не сказано, что ВСЕ гантели должны быть разложены по кучками. Впрочем, тут я соглашусь, что это явно подразумевается...


p.s. и ещё хочу предостеречь/проинформировать: ваша задачка совсем на так проста, как она кажется на первый взгляд!

Думал все это будет очевидно. Да, знаю, что задачка трудновата. Пытаюсь найти самое оптимальное решение)

[Аватар]

Насчет оптимальности не думал, но идея тупого перебора зашкаливает - представьте 100 гирь и число сочетаний 50 из них

[Poma][a]

Пусть вес i-той гантели. Тогда W - сумма всех w[i] от 1 до n
Всего гантелей n -> делители числа W - возможные варианты разбиения
При чтении сразу найдем Min и Max последовательности. И теперь проверяем делители числа W из диапазона [Min, Max}

[fourston]

Сообщение от Poma][a

Пусть вес i-той гантели. Тогда W - сумма всех w[i] от 1 до n
Всего гантелей n -> делители числа W - возможные варианты разбиения
При чтении сразу найдем Min и Max последовательности. И теперь проверяем делители числа W из диапазона [Min, Max}

Это ясно, спасибо, а можно вывести две отсортированные кучки?

[Аватар]

Ромаха, идею не понял. 1+3+5+7=16, разбиение 1+7 = 3+5. Где там делители 16?

[Poma][a]

1+7=3+5 = 8
16 / 2 = 8