#algorithm #puzzle #partitioning
#алгоритм #Головоломка #разделение
Вопрос:
Вот вопрос:
Учитывая отсортированный список, скажем, целых чисел (вы можете предположить, что они положительные, если это упрощает задачу), разделите список на ‘n’ разделов одинакового размера (или как можно более равных), при условии, что ни одно из целых чисел не отображается более чем в одном таком разделе.
Ограничение по сути означает, что если у вас есть список {1,1,2,2}
тогда все они должны быть в одном наборе, и все 2 должны быть в одном наборе. Все 1 и все 2 также могут быть в одном наборе. Но у нас не может быть одного из 1 в первом разделе, а второго 1 во втором разделе.
Пример 1:
List: {1,1,2,2,3,3,4,4}
Number of partitions to make: 4
Answer: {1,1} {2,2} {3,3} {4,4}
Example 2: (trickier one)
List: {1,1,2,2,2,3,3,4,4,4,4,4,4,4,4}
Number of partitions to make : 3
Answer: {1,1,2,2} {3,3} {4,4,4,4,4,4,4,4}
OR: {1,1} {2,2,3,3} {4,4,4,4,4,4,4,4}
Обратите внимание, что 3-й раздел должен иметь размер 8, потому что из-за ограничения все 4 должны находиться в одном разделе.
Может быть множество других сложных случаев. Дайте мне знать, если кому-нибудь нужны дополнительные примеры.
Итак, вопросы в том, каков наилучший способ приблизиться или решить эту проблему?
Ответ №1:
Самое простое решение, о котором я могу думать, это,
-
Сначала найдите все одинаковые элементы в списке (используйте что-то вроде хэширования, чтобы найти их, или подсчитайте сортировку, если вы заранее знаете диапазон), а также сохраните их размер.
-
Теперь у вас будут наборы повторяющихся чисел (например, {1,1} {2,2}). После этого шага попробуйте найти количество списков, которые у вас есть, и сгруппируйте их, чтобы сформировать n количество разделов (как указано в постановке задачи). Например В вашем последнем сложном примере в итоге у нас будет 4 списка, вам нужно 3 раздела. Вы можете найти 2 небольших списка и объединить их в форму 1, повторяйте это, пока не достигнете требуемого количества разделов.
Комментарии:
1. Хорошо, вот встречный пример вашего решения. Предположим, у нас есть {1,1,1,1,1,1,1} {2,2,2,2,2,2,2} {3,3,3,3,3,3} {4,4,4,4,4,4} По сути, это означает, что на первом шаге у вас есть разделы размером 7,7,6,6. Теперь нам нужны 2 раздела из них. Итак, на следующем шаге вы сделаете что-то вроде 7,7,12. Затем вы выполните 14, 12 и выведете это в качестве ответа. Но лучшим ответом было бы 13,13
Ответ №2:
Это скрытая версия проблемы с k-разделением или проблемы с упаковкой бина. Если вы подсчитываете количество вхождений каждого элемента и помещаете эти значения в мультимножество, то вы в основном пытаетесь разделить эти числа на наборы, которые имеют одинаковую сумму.
Если n = 2, для этого есть несколько псевдополиномиальных алгоритмов. В противном случае не существует известных псевдополиномиальных алгоритмов. (и не может быть, если P = NP)
Что касается того, как к нему подойти. Если вы можете выбрать n, просто установите его равным 1 и разделите список на себя. Если вы этого не делаете, но у вас есть небольшие списки, просто реализуйте решение методом перебора. Если вы не выбираете n, и у вас длинные списки, изучите алгоритмы жадности / приближения и попытайтесь точно определить, что вы подразумеваете под "как можно более равным". (Вы имеете в виду максимальную разницу? Разница? что-то еще?)
Удачи.