CD
Алексей
И вопрос: Как растет число возможных разностей между суммами элементов подмножеств с ростом числа элементов исходного множества? Это квадрат? N*N?
Вопрос непонятен, очевидно что это просто 2^(N - 1) для k = 2
Size: a a a
2020 September 08
DY
Алексей
Ребята, есть задача, прошу помочь! Задано некоторое множество, например [1,2,3,4,5,6,10], задано число подмножеств - k, на которые надо разбить это множество. Нужно разбить исходное множество на k подмножеств таким образом, чтобы разность сумм элементов любых двух подмножеств была минимальна. Например, [10],[4,6],[1,2,3,5] - Максимальная разность сумм равна 1.
В случае k = 2 это эквивалентно задаче о рюкзаке. Значит быстрого алгоритма не существует. Перебор, Динамическое программирование, Линейное программирование.
А
В случае k = 2 это эквивалентно задаче о рюкзаке. Значит быстрого алгоритма не существует. Перебор, Динамическое программирование, Линейное программирование.
Если k любое то это близко к задаче планирования. Например, multi-processor
scheduling. Есть k процессоров и нужно распределить задачи так, чтобы нагрузить их одинаковым образом. Но вопрос не в том как решать.
scheduling. Есть k процессоров и нужно распределить задачи так, чтобы нагрузить их одинаковым образом. Но вопрос не в том как решать.
DY
Алексей
Если k любое то это близко к задаче планирования. Например, multi-processor
scheduling. Есть k процессоров и нужно распределить задачи так, чтобы нагрузить их одинаковым образом. Но вопрос не в том как решать.
scheduling. Есть k процессоров и нужно распределить задачи так, чтобы нагрузить их одинаковым образом. Но вопрос не в том как решать.
Может по разному расти в зависимости от самих элементов. Если, например, элементы — это степени двойки, то все разности будут получаться различными и их будет 2^(n-1).
DY
Или 2^n, если разрешить пустые множества
DY
А если все элементы одинаковы, например все равны 1, то будет линейно
П
Как это решать? В двух словах
SC
Тут без 8 слов не обойдешься.
PO
Думаю, бан
PO
Или там этот отбор закончился?
P
Уже закончился: это на прошлое лето
P
но даже если и нет, то почему бан?
П
А где правила почитать? Чтоб не залететь?
PO
но даже если и нет, то почему бан?
Потому что если не закончился - то нехер задачи палить
PO
Если закончился, то ничего страшного
PO
А где правила почитать? Чтоб не залететь?
Нельзя спрашивать о задачах идущих контестов
P
Нельзя спрашивать о задачах идущих контестов
Это есть в правилах этого чата?
P
Как это решать? В двух словах
Сейчас поищу решение - писал тогда контест
MB
Это есть в правилах этого чата?
Это подразумевается
MB
Если авторы контеста запрещают обсуждать его задачи, то их нельзя обсуждать нигде, в том числе в этом чате.