Единый целочисленный делитель

Question

Проблема выглядит следующим образом: Вы должны нарисовать линию шириной N px в виде M равномерных штрихов.

Если, например, N = 13 и M = 5, у вас будет тире шириной 2 пикселя, а у нас будет ошибка 3 пикселя.

Мы можем сделать лучше, мы можем рисовать штрихи следующей ширины: 3, 3, 3, 2, 2.Но мы можем сделать еще лучше, чтобы штрихи могли иметь следующую ширину: 3, 2, 3, 2, 3.

Если у меня есть список a = (3, 3, 3, 2, 2), как я могунайти такой список, чтобы расстояние 'D' между всеми парами в списке было максимальным?

В этом примере D (a) = 0 + 0 + 1 + 0 = 1. Для списка b = (3,2, 3, 2, 3), D (b) = 1 + 1 + 1 + 1 = 4.

Какой самый быстрый / простой метод?

Answer 1

Самый простой метод, который я знаю?Использование чисел с плавающей точкой ...

В Python:

def pace(D,M): return [round(float(D) / M * i) for i in range(1,M+1)]

Я уже видел это где-то здесь, я думаю.

Answer 2

Что-то вдохновленное алгоритмом Брезенхема должно сработать. Поверьте, вы не хотите максимизировать D во всех перестановках вашего набора. Эта проблема слишком сложна (сложность O (n!), Поэтому, если n не очень мало, это не сработает)