Как перебрать все сочетания?

Question

[Даниил Демидко]

О сочетаниях я знаю отсюда.
Передо мной сейчас стоит такая задача - есть набор чисел. Из них нужно выбрать сочетание, сумма цифр которого нечётна и наибольшая среди нечетных сочетаний. Каким алгоритмом можно перебрать все сочетания? В какую сторону копать?

Answer 1

[Антон Федорян]

Зачем перебирать все сочетания?
Отсортировать набор цифр.
Взять указанное количество самых больших
Если их сумма четная - заменить самую младшую на предыдущую из списка пока сумма не станет нечетной.
n = [1, 5, 3, 4, 9, 7, 6]
k = [3]
n_sort = [1, 3, 4, 5, 6, 7, 9]
k_sum = 6 + 7 + 9 = 22 - четное число
Меняем 6 на 5, k_sum = 5+ 7 + 9 = 21 - PROFIT!

Comments

[Даниил Демидко]

Премного благодарен

[res2001]

А почему вы берете 3 цифры? В условии задачи не задано количество цифр в сочетании. Поэтому оно может быть максимальным - вплоть до всех цифр в наборе.
Поэтому надо найти сумму всех цифр, так же надо считать количество нечетных цифр в сумме и найти минимальное нечетную цифру.
Если количество нечетных цифр четное, то минимальную нечетную цифру вычесть из суммы.
Вариантов максимальных сочетаний 2 - либо все цифры, либо все - максимальная нечетная.
Сортировать при этом не нужно.

[res2001]

эээ .. не нужно считать количество не четных. То же самое можно сделать просто проанализировав на четность полученную сумму. Если сумма четная - вычесть минимальное не четное.

Answer 2

[x67]

1. Анализ. Каковы свойства появления нечетных чисел? Ч+Ч=Ч; НЧ+НЧ=Ч; НЧ+Ч=НЧ. Бинго! Исходя из вышесказанного, нам нужно сложить сколь угодно четных чисел и нечетное количество нечетных чисел.
2. Определяемся со свойствами наборов. Сколько цифр? А цифры ли это или числа?
3. Когда задача будет однозначно и четко поставлена, не составит труда сначала отфильтровать наборы, которые не дают в сумме нечетное число, затем те, чьи цифры/числа не являются достаточно высокими (выше среднего, к примеру), а из оставшегося множества уже простым перебором найти наибольшую сумму.

Answer 3

[Владислав]

Вообще сочетания можно for'ом или рекурсией обойти.
Но чувствуется, что задача должна решаться проще, хотя по тому, что написано в вопросе сложно судить.