Если вы слышали о линейном программировании (LP) и его «двоюродных братьях» (ILP, MILP), это может быть хорошим подходом, чтобы помочь вам решить вашу проблему с большой эффективностью.
AЛинейная программа состоит из набора переменных (ваша матрица неизвестна), ограничений (максимальные значения, сумма строк и столбцов) и целевой функции (здесь нет) для минимизации или максимизации.
Давайте назовем x [i] [j] значения, которые вы ищете.Со следующими данными:
NxM размеры вашей матрицы
max_val[i][j] максимальное значение для переменной x[i][j]
row_val[i] сумма значений в строке i
col_val[j] сумма значений в столбце j
Тогда возможная линейная программа, которая может решить вашу проблему:
// declare variables
int x[N][M] // or eventually float x[N][M]
// declare constaints
for all i in 1 .. N, j in 1 .. M, x[i][j] <= max_val[i][j]
for all i in 1 .. N, sum[j in 1 .. M](x[i][j]) == row_val[i]
for all j in 1 .. M, sum[i in 1 .. N](x[i][j]) == col_val[j]
// here the objective function is useless, but you still will need one
// for instance, let's minimize the sum of all variables (which is constant, but as I said, the objective function does not have to be useful)
minimize sum[i in 1 .. N](sum[j in 1 .. M](x[i][j]))
// you could also be more explicit about the uselessness of the objective function
// minimize 0
Решатели, такие как gurobi или Cplex (но их гораздо больше, см., например, здесь ), можно решить такие проблемы невероятно быстро, особенно если ваши решения не нужнобыть целым числом, но может быть плавающим (что делает проблему намного, намного легче).Он также имеет преимущество, заключающееся в том, что он не только быстрее выполняется, но и быстрее и проще в коде.У них есть API-интерфейсы на нескольких распространенных языках программирования для упрощения их использования.
Например, вы можете разумно ожидать, что сможете решить эту проблему менее чем за минуту, с сотнями тысяч переменных в целочисленном случае, миллионами в реальномрегистр переменных.
Редактировать: В ответ на комментарий приведен фрагмент кода в OPL (язык, используемый Cplex и другими решателями LP), который решит вашу проблему.Мы рассматриваем случай 3х3.
// declare your problem input
int row_val[1..3] = [7, 11, 8];
int col_val[1..3] = [14, 6, 6];
int max_val[1..3][1..3] = [[10, 10, 10], [10, 10, 10], [10, 10, 10]];
// declare your decision variables
dvar int x[1..3][1..3];
// objective function
minimize 0;
// constraints
subject to {
forall(i in 1..3, j in 1..3) x[i][j] <= max_val[i][j];
forall(i in 1..3) sum(j in 1..3) x[i][j] == row_val[i];
forall(j in 1..3) sum(i in 1..3) x[i][j] == col_val[j];
}
Концепция решателя LP заключается в том, что вы описываете только проблему, которую хотите решить, а затем решатель решает ее за вас.Проблема должна быть описана в соответствии с определенным набором правил.В текущем случае (целочисленное линейное программирование, или ILP) все переменные должны быть целыми числами, а ограничения и целевая функция должны быть линейными равенствами (или неравенствами) по отношению к переменным решения.
Тогда решатель будет работать какчерный ящик.Он проанализирует проблему, запустит алгоритмы, которые могут ее решить, с кучей оптимизаций, и выведет решение.