Переупорядочивайте элементы в списках, чтобы привести их средние значения в соответствие

На самом деле это не вопрос программирования, на самом деле это скорее алгоритмический вопрос. Одно из моих требований к функциональности требует от меня ограничить разницу средних значений определенным диапазоном.

Возьмем, к примеру:

a: {1, 2, 3, 4, 5}    // avg: 3
b: {2, 3, 3, 4, 6}    // avg: 3.4
c: {4, 4, 5, 7, 6}    // avg: 5.2

Если максимальная разница средних была 2, то:

  • Разница между средними значениями a и b будет допустимой.
  • Разница между средними значениями b и c будет допустимой.
  • Разница между средними значениями a и c недействительна.

Затем мне нужно изменить порядок (например, поменять местами 1 с a на 7 с b, чтобы средние значения стали ближе друг к другу, а их различия были в пределах указанного максимума.

Тогда мой вопрос: как я могу наиболее эффективно (с наименьшим количеством ходов) переставить элементы так, чтобы средние значения сходились в пределах указанной максимальной средней разницы?

На самом деле я не ищу однозначного ответа, но если кто-то имеет представление о том, что мне следует искать, я был бы более чем счастлив услышать от вас. Если это не относится к StackOverflow, мои извинения, возможно, вы могли бы направить меня в другое место?

Большое вам спасибо за ваше время!


person matt    schedule 22.06.2014    source источник
comment
На самом деле это не вопрос программирования. Тогда это не совсем по теме.   -  person Jonathon Reinhart    schedule 22.06.2014
comment
Этот вопрос кажется не по теме, потому что это не вопрос программирования   -  person L.B    schedule 22.06.2014
comment
У вас есть справочное среднее значение или только максимальное значение разницы?   -  person HuorSwords    schedule 22.06.2014
comment
@JonathonReinhart Может быть, тег алгоритма следует удалить из stackoverflow?   -  person Tarik    schedule 23.06.2014
comment
Вы уверены, что вам разрешено менять местами номера, расположенные в разных позициях в двух разных массивах? Это ограничение еще больше уменьшит пространство поиска.   -  person Tarik    schedule 23.06.2014


Ответы (1)


Сначала просуммируйте все числа, затем разделите сумму на количество массивов. В этом примере у нас 59/3

Результат целочисленного деления будет использоваться для определения размера каждого рюкзака, скорректированного таким образом, чтобы сумма размеров рюкзаков соответствовала сумме всех чисел. В этом примере размеры ранца 19, 20 и 20.

Затем найдите все решения проблемы с несколькими рюкзаками.

Наконец, оптимальным является решение, которое может быть достигнуто за наименьшее количество ходов от начального состояния.

person Tarik    schedule 22.06.2014
comment
Это кажется надежным и простым в реализации решением, но, к сожалению, я думаю, что оно делает мою максимальную среднюю разницу бесполезной? Или мне что-то здесь не хватает? - person matt; 23.06.2014
comment
Сопоставление вашей проблемы с несколькими рюкзаками означает, что вам нужно решить полную задачу NP. Это нормально для небольших наборов данных, но для больших вы вынуждены использовать эвристику и попадаете на неоптимальное решение. Цель того, что я представил, - показать, что ваша карта соответствует стандартной известной проблеме известной сложности. - person Tarik; 23.06.2014
comment
Другая причина заключалась в том, чтобы показать, что нужно решать две задачи за одну. Множественный рюкзак + минимальное количество свопов. Если подумать, поскольку количество элементов в каждом рюкзаке должно быть одинаковым (поскольку при подкачке количество элементов каждого набора остается неизменным), пространство поиска значительно сокращается. - person Tarik; 23.06.2014
comment
Это будет означать, что 59 вы выбрали 19 для первого рюкзака, а затем 40 выбрали 20 для второго. Это количество комбинаций. - person Tarik; 23.06.2014
comment
Еще один момент, который я хотел бы отметить, заключается в том, что если вы меняете числа в сторону меньшей разницы в среднем при каждом обмене, следуя жадному подходу, вы можете застрять в локальных оптимумах. - person Tarik; 23.06.2014
comment
Я также хотел бы указать вам на алгоритм программирования ограничений, который может дать вам другую перспективу. - person Tarik; 23.06.2014