Разбиение числа на несколько почти равных частей

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

_{(источник: codecogs.com)}
.

В этом случае n будет числом факторов, которые вы используете, чтобы попытаться разложить свое число на составляющие. Каждый x_i является особым фактором в общей сумме значения, которое вы хотите разложить. Я также собираюсь предположить, что ни один из факторов не может быть с плавающей запятой, а может быть только целым числом. Таким образом, вам нужно использовать особый случай линейного программирования, называемый целочисленным программированием, где ограничения и фактическое решение вашей проблемы все в целых числах. В общем случае задача целочисленного программирования формулируется так:

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

У вас есть неравенства, равенства, а также границы x, которые должен соблюдать каждый параметр в вашем решении. Вам также необходимо убедиться, что каждый параметр x является целым числом. Таким образом, в MATLAB есть функция с именем intlinprog, которая будет выполнять это для ты. Однако эта функция предполагает, что вы минимизируете целевую функцию, поэтому, если вы хотите максимизировать, просто минимизируйте отрицательное значение. f – это вектор весов, который будет применяться к каждому значению в вашем векторе параметров, и с нашей целевой функцией вам просто нужно установить все эти значения в -1.

Поэтому, чтобы сформулировать свою проблему в рамках целочисленного программирования, вы фактически делаете:

_{(источник: codecogs.com)}

V будет значением, которое вы пытаетесь разложить (например, 300).

Стандартный способ вызова intlinprog заключается в следующем:

x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub);

f — это вектор, который взвешивает каждый параметр решения, которое вы хотите решить, intcon обозначает, какие из ваших параметров должны быть целыми числами. В этом случае вы хотите, чтобы все они были целыми числами, поэтому вам нужно будет предоставить возрастающий вектор от 1 до n, где n — это количество факторов, на которые вы хотите разложить число V (так же, как и раньше). A и b — это матрицы и векторы, которые определяют ваши ограничения неравенства. Поскольку вы хотите равенства, вы должны установить это пустым ([]). Aeq и beq такие же, как A и b, но для равенства. Поскольку здесь у вас есть только одно ограничение, вы просто создадите матрицу из 1 строки, где каждое значение равно 1. beq будет единственным значением, обозначающим число, которое вы пытаетесь разложить на множители. lb и ub — это нижняя и верхняя границы для каждого значения в наборе параметров, с которым вы ограничиваетесь, поэтому это будет 60 и 80 соответственно, и вам нужно будет указать вектор, чтобы гарантировать, что каждое значение параметров ограничено между этими двумя диапазонами.

Теперь, поскольку вы не знаете, сколько факторов будет равномерно разлагать ваше значение, вам придется зацикливаться на заданном наборе факторов (например, от 1 до 10, или от 1 до 20 и т. д.), поместите свои результаты в массив cell, затем вам придется вручную проверить себя, было ли успешно целочисленное разложение.

num_factors = 20; %// Number of factors to try and decompose your value
V = 300;
results = cell(1, num_factors);

%// Try to solve the problem for a number of different factors
for n = 1 : num_factors
    x = intlinprog(-ones(n,1),1:n,[],[],ones(1,n),V,60*ones(n,1),80*ones(n,1));
    results{n} = x;
end

Затем вы можете просмотреть results и посмотреть, какое значение n помогло разложить ваше число на указанное количество факторов.

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

Однако intlinprog был выпущен только в последних версиях MATLAB. Если вы хотите сделать то же самое без него, вы можете использовать linprog, которая представляет собой версию целочисленного программирования с плавающей запятой... на самом деле, это просто основная структура линейного программирования. Вы бы назвали linprog таким образом:

x = linprog(f,A,b,Aeq,beq,lb,ub);

Все переменные одинаковы, за исключением того, что intcon здесь не используется... что имеет смысл, поскольку linprog может генерировать числа с плавающей запятой как часть своего решения. Из-за того, что linprog может генерировать решения с плавающей запятой, вы можете сделать это, если хотите убедиться, что для заданного значения n вы можете перебрать свои результаты, взять пол результата и вычесть с окончательным результатом, и просуммировать результат. Если вы получаете значение 0, это означает, что вы получили полностью целочисленный результат. Поэтому вам нужно будет сделать что-то вроде:

num_factors = 20; %// Number of factors to try and decompose your value
V = 300;
results = cell(1, num_factors);

%// Try to solve the problem for a number of different factors
for n = 1 : num_factors
    x = linprog(-ones(n,1),[],[],ones(1,n),V,60*ones(n,1),80*ones(n,1));
    results{n} = x;
end

%// Loop through and determine which decompositions were successful integer ones
out = cellfun(@(x) sum(abs(floor(x) - x)), results);

%// Determine which values of n were successful in the integer composition.
final_factors = find(~out);

final_factors будет содержать указанное вами количество факторов, которые были успешными в целочисленной декомпозиции. Теперь, если final_factors пусто, это означает, что не удалось найти ничего, что могло бы разложить значение на целочисленные множители. Отметив описание вашей проблемы, вы сказали, что можете допускать допуски, поэтому, возможно, просмотрите results и определите, какая общая сумма лучше всего соответствует значению, а затем выберите любое количество факторов, которые дали вам этот результат, в качестве окончательного ответа.

Теперь, обращая внимание на мои комментарии, вы увидите, что эта проблема очень не ограничена. Вы не знаете, сколько факторов требуется для получения целочисленной декомпозиции вашего значения, поэтому нам пришлось использовать полугрубую силу. Фактически, это более общий случай проблемы суммы подмножества. Эта проблема является NP-complete. По сути, это означает, что неизвестно, существует ли алгоритм с полиномиальным временем, который можно использовать для решения такого рода задач, и что единственный способ получить правильное решение — перебрать каждое возможное решение и проверить, работает с указанной проблемой. Обычно перебор решений требует экспоненциального времени, что очень сложно для больших задач. Еще один интересный факт заключается в том, что современные криптографические алгоритмы используют NP-полную неразрешимость как часть своего зашифрованного текста и шифрования. По сути, они делают ставку на тот факт, что единственный способ определить правильный ключ, который использовался для шифрования обычного текста, — это проверить все возможные ключи, что является неразрешимой проблемой... особенно если вы используете 128-битный код. шифрование! Это означает, что вам придется проверить 2^128 возможности, и, если предположить, что компьютер умеренно быстрый, в худшем случае время на поиск правильного ключа займет больше, чем текущий возраст Вселенной. Прочтите этот классный пост в Википедии для получения более подробной информации о неподатливости в отношении взлома ключей в криптографии. .

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

В Математическом институте Клэя есть так называемые задачи тысячелетия. сайт, вы получите миллион долларов.

Кроме того, это для каждой проблемы, так что one problem solved == 1 million dollars!

_{(источник: quickmeme.com )}