Алгоритм вычисления числа комбинаций для формирования 100

Если вам нужно разделить 100 на 2 с максимальным расстоянием N, наименьшее значение в комбинации будет

100/2 - N / 2

Если вам нужно разделить 100 на 3 значения с максимальным расстояние N, это становится более сложным. Среднее из трех значений будет 100/3, но если одно из них намного ниже, чем это среднее, то другое может быть только немного больше, чем это среднее, что означает, что минимальное значение не является средним минус максимальное разделенное расстояние. на два, но, вероятно,

100/3 - 2N / 3

Как правило, со значениями M это становится

100 / M - (M-1) N / M

Что можно упростить до

​​(100 - (M-1) N) / M

Аналогичным образом мы можем вычислить максимально возможное значение:

(100 + (M-1) N) / M

Это дает вам диапазон для первое значение вашей комбинации.

Чтобы определить диапазон для второго значения, вы должны учитывать следующие ограничения:

• расстояние с первым значением (не должно быть выше вашего максимального расстояния)
• можем ли мы все же достичь суммы (100 )

Первое ограничение не проблема. Вторая есть.

Предположим, что мы делим 100 на 3 с максимальным расстоянием 30, используя число, кратное 10. Как было вычислено ранее, минимальное значение:

(100 - (3-1) 30) / 3 -> 13 -> округлено до следующего кратного 10 -> 20

Максимальное значение -

(100 + (3-1) 30) / 3 -> 53 -> округлено до предыдущего кратного 10 -> 50

Таким образом, для первого значения мы должны перебрать 20, 30, 40 и 50.

Предположим, мы выбрали 20. Осталось 80 для двух других значений.Снова мы можем распределить 80 по 2 значениям с максимальным расстоянием 30, это дает:

Минимум: (80 - (2-1) 30) / 2 -> 25 -> округлено -> 30

Максимум: (80 + (2-1) 30) / 2 -> 55 -> округлено -> 50

Второе ограничение состоит в том, что мы не хотим, чтобы расстояние было больше 30 по сравнению с нашим первым значением. Это дает минимум -10 и максимум 50.

Теперь возьмите пересечение между обоими доменами -> от 30 до 50 и для второго значения повторите 30, 40, 50.

Затем повторите это для следующее значение.

РЕДАКТИРОВАТЬ: Я добавил алгоритм в псевдокоде, чтобы было понятнее:

calculateRange (vector, remainingsum, nofremainingvalues, multiple, maxdistance)
{
if (remaingsum==0)
   {
   // at this moment the nofremainingvalues should be zero as well
   // found a solution
   print vector
   return;
   }

minvalueaccordingdistribution = (remainingsum-(nofremainingvalues-1)*maxdistance)/nofremaingvalues;
maxvalueaccordingdistribution = (remainingsum+(nofremainingvalues-1)*maxdistance)/nofremaingvalues;

minvalueaccordingdistance = max(values in vector) - maxdistance;
maxvalueaccordingdistance = min(values in vector) + maxdistance;

minvalue = min (minvalueaccordingdistribution, minvalueaccordingdistance);
maxvalue = max (minvalueaccordingdistribution, minvalueaccordingdistance);

for (value=minvalue;value<=maxvalue;value+=multiple)
   {
   calculaterange (vector + value, remainingsum - value, nofremainingvalues-1, multiple, maxdistance);
   }
}

main()
{
calculaterange (emptyvector, 100, 2, 20);
}

Ввод: (2-10-20)

1. Разделите число на параметр 1

(50,50)

2 Проверьте, допускает ли правило разности эту комбинацию. Если это нарушает правило, то СТОП, если позволяет, затем добавьте это и его комбинации в список результатов

Например: abs (50-50) <20, так что все в порядке

3 Увеличьте первое значение на параметр 2, уменьшите второе значение на параметр 2

4. Перейти 2. точка

Почему нельзя использовать метод грубой силы с небольшой оптимизацией? Например, скажите N - количество комбинаций M - кратные D - Максимально возможное расстояние

Таким образом, возможные значения в комбинациях могут быть M, 2M, 3M и так далее. Вам нужно сгенерировать этот набор, а затем начать с первого элемента из набора и попытаться найти следующие два, выбирая значения из того же набора (при условии, что они должны быть меньше D от первого / второго значения).Таким образом, с i / p 3-10-30

1. Создайте набор из 10, 20, 30, 40, 50, 60, 70, 80, 90 в качестве возможных значений
2. Начните с 10, выберите второй значение должно быть 20, 30, 40, 50 (D <30)
3. Теперь выберите второе значение из набора 20, 30, 40, 50 и попробуйте получить следующее значение и так далее

Если вы используете рекурсию тогда решение стало бы еще проще.

1. Вы должны найти N значений из список возможных значений в пределах MIN & Индекс MAX.
2. Итак, попробуйте первое значение в Индекс MIN (до индекса MAX). Скажи мы выбрали значение по индексу X.
3. Для каждого первого значения попытайтесь найти из N-1 значений из списка, где MIN = X + 1 и МАКС.

Наихудшая производительность будет, когда M = 1 и N достаточно велико.

Является ли расстояние между всеми аддитивными коэффициентами или между каждым из них? Например, при 3-10-20 [20-40-60] правильный ответ? Я предполагаю второе, но приведенное ниже решение можно довольно тривиально изменить, чтобы оно работало для первого.

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

Попробуем разместить числа как можно ниже, за исключением последнего, которое будет как можно более высоким (при условии, что остальные низкие). Пусть общий делитель равен d , и разделим на него 100 , так что мы имеем S = 100 / d . Это хорошо квантует нашу проблему. Теперь у нас есть ограничение, что интервал составляет не более s , за исключением того, что мы преобразуем его в число квантованных шагов, n = s / d . Теперь предположим, что у нас есть M выборок, i1 ... iM и запишем ограничения:

i1 + i2 + i3 + ... + iM = S
0 <= i1 <= n
0 <= i2 <= n
. . .
0 <= iM <= n
i1 <= i2
i2 <= i3
. . .
i(M-1) <= iM

Мы можем решить первое уравнение, чтобы получить iM с учетом остальных .

Теперь, если мы сделаем все как можно более похожим:

i1 = i2 = ... = iM = I
M*I = S
I = S/M

Очень хорошо - у нас есть отправная точка! (Если I является дробью, сделайте первые несколько I , а остаток I + 1 .) Теперь мы просто попытаемся пройти по каждой переменной по очереди:

for (i1 = I-1 by -1 until criteria fails)
  sum needs to add to S-i1
  i2 >= i1
  i2 <= i1 +n
  solve the same problem for M-1 numbers adding to S-i1
  (while obeying the above constraint on i2)

Послушайте, у нас есть рекурсивный алгоритм! Мы просто проходим и зачитываем ответы.

Конечно, мы могли бы пройти i1 вверх, а не вниз. Если вам нужно распечатать ответы, можете это сделать.Если вам просто нужно их посчитать, обратите внимание, что подсчет является симметричным, поэтому просто удвойте ответ, который вы получите при обратном отсчете. (У вас также будет поправочный коэффициент, если не все значения начинались одинаково - если некоторые из них были I , а некоторые были I + 1 , вам необходимо принять это во внимание, что Я не буду здесь делать.)

Редактировать: Если это диапазон, в который должно уместиться каждое значение, вместо всех

0 <= i1 <= n

условий, у вас есть

max(i1,i2,...,iM) - min(i1,i2,...,iM) <= n

Но это дает то же рекурсивное условие, за исключением того, что мы передать максимальные и минимальные значения тех элементов, которые мы уже выбрали для добавления в микс, вместо того, чтобы добавлять ограничение на i2 (или какую бы другую переменную ни ходили).