Алгоритм переупорядочения последовательности весов

Question

У меня есть несколько элементов в массиве, каждый из которых связан с определенным весом. Существует бизнес-правило, гласящее, что никакие два смежных элемента не могут иметь общий вес больше определенного значения, скажем, 100 для простоты.

Например, все в порядке:

[40,60,40,50]

Но не этот (так как 50 + 60 = 110)

[50,60,40] 

Я пытаюсь реализовать алгоритм, который будет переставлять элементы (если это возможно), чтобы бизнес-правило выполнялось. Например, второй может быть переставлен в [60,40,50] или [50,40,60]

Алгоритм также должен сводить к минимуму количество перемещаемых элементов, т. Е. Первое решение, приведенное выше, является наиболее подходящим, поскольку сохраняется «подстановка» [60,40].

Я не ищу полный ответ или примеры кода, но был бы рад, если бы кто-то мог указать некоторые алгоритмы или категории алгоритмов для этой цели. Было бы намного лучше полагаться на существующий и проверенный алгоритм, чем на некоторые домашние вещи.

Примечание: На самом деле количество предметов очень велико, поэтому тестирование всех различных перестановок НЕ вариант.

Answer 1

Приятное жадное решение: за первое место возьмите максимальное количество. За каждое следующее место возьмите максимум из неиспользованных номеров до того, как удовлетворят ваше условие Если вы разместите все цифры - вы нашли решение. В противном случае решение не существует, почему - это упражнение для вас.

Мое доказательство: представьте, что решение существует. Покажите, что мой алгоритм его найдет. Давайте a_1, ..., a_n - любое решение. Пусть a_i - максимальный элемент. Тогда a_i, a_ {i-1}, ..., a_1, a_ {i + 1}, a_ {i + 2}, ..., a_n также является решением, потому что a_1 <= a_i, a_1 + a_ { i + 1} <= a_i + a_ {i + 1}, поэтому (a_i, a_ {i + 1}) - хорошая пара. Далее, пусть a_1, ..., a_j это элемент согласно моему решению. Покажите, что a_ {j + 1} может быть элементом, как предполагает мое решение. Пусть a_i - максимум из a_ {j + 1}, .., a_n. Тогда a_1, ..., a_j, a_i, a_ {i-1}, ..., a {j + 1}, a_ {i + 1}, ..., a_n также является решением. Это показывает, что алгоритм всегда находит решение. </p>

Answer 2

Большие предметы могут быть только рядом с мелкими.

1. Сортировка списка
2. Разрезать пополам
3. Обратная вторая половина
4. Поменяться половинками
5. Перемешать (возьмите первый предмет из каждой половины, повторите)

Пример: [1,3,8,4,2,4,1,7]

1. [1,1,2,3,4,4,7,8]
2. [1,1,2,3] [4,4,7,8]
3. [1,1,2,3] [8,7,4,4]
4. [8,7,4,4] [1,1,2,3]
5. [8,1,7,1,4,2,4,3]

Я почти уверен, что вы не можете добиться большего успеха, чем это. Если бизнес-правило нарушается, решения не существует. Докажи / Контрпример оставил как упражнение; -)

Редактировать: Сначала возьмите самый большой предмет!

Answer 3

Это похоже на проблему с упаковкой бункера, посмотрите (например) http://en.wikipedia.org/wiki/First_fit_algorithm

Я почти уверен, что это не то же самое, но это может дать вам некоторые подсказки.

Вам также нужно подумать о том, что произойдет, если предмет сигилы превысит лимит - как бы вы справились с этим?

Answer 4

Если вы читаете данные из файла данных и находите исключение (значение, превышающее целевое значение), вы можете либо убить программу, либо исключить ее. Кроме того, решение, предоставляемое LumpN, можно настроить, переключив последний шаг, если предыдущее решение не удалось. В основном шаркает назад.