#c# #algorithm #sorting #average
#c# #алгоритм #сортировка #среднее
Вопрос:
На самом деле это не вопрос программирования, на самом деле это скорее алгоритмический вопрос. Одно из моих функциональных требований требует от меня ограничить разницу средних значений в пределах определенного диапазона.
Возьмем, к примеру:
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, мои извинения, возможно, вы могли бы направить меня в другое место?
Большое вам спасибо за ваше время!
Комментарии:
1. «На самом деле это не вопрос программирования» — тогда это не совсем по теме.
2. Этот вопрос кажется не по теме, потому что это не вопрос программирования
3. Есть ли у вас эталонное среднее значение или только максимальное значение разницы?
4. @JonathonReinhart Может быть, тег алгоритма следует удалить из stackoverflow?
5. Вы уверены, что вам разрешено менять местами числа, расположенные в разных позициях в двух разных массивах? Это ограничение еще больше сократит пространство поиска.
Ответ №1:
Сначала просуммируйте все числа, затем разделите сумму на количество массивов. В этом примере у нас 59/3
Результат целочисленного деления будет использоваться для определения размера каждого рюкзака, скорректированного таким образом, чтобы сумма размеров рюкзаков соответствовала сумме всех чисел. В этом примере размеры рюкзака равны 19, 20 и 20.
Затем найдите все решения проблемы с несколькими рюкзаками.
Наконец, оптимальным является решение, которое может быть достигнуто с наименьшим количеством переходов из начального состояния.
Комментарии:
1. Это кажется надежным и простым в реализации решением, но, к сожалению, я думаю, что это делает мою максимальную среднюю разницу бесполезной? Или я что-то здесь упускаю?
2. Сопоставление вашей проблемы с несколькими ранцами означает, что вам нужно решить NP-полную задачу. Это нормально для небольших наборов данных, но для больших вы вынуждены использовать эвристику и принимать неоптимальное решение. Цель того, что я представил, — показать, что ваши карты соответствуют стандартной известной задаче с известной сложностью.
3. Другая причина заключалась в том, чтобы показать, что вам нужно решить две проблемы в одной. Несколько ранцев минимальное количество обменов. Подумав об этом, поскольку количество элементов должно быть одинаковым в каждом рюкзаке (поскольку замена оставляет количество элементов каждого набора как есть), пространство поиска значительно сокращается.
4. Это означало бы, что вы бы 59 выбрали 19 для первого рюкзака, затем 40 выбрали 20 для второго. Это количество комбинаций.
5. Еще один момент, на который я хотел бы обратить внимание, это то, что если вы меняете местами числа в сторону меньшей разницы в среднем при каждом обмене, следуя жадному подходу, вы можете застрять в локальных оптимумах.