基于线性方程计算值的算法

Question

我正在使用java基于线性方程计算PayStructure中各种Paycodes的值。我的不同方程如下：

CTC = Fixed Value

Basic = CTC * 0.4

HRA = Basic/2

ConveyanceAllowance = Fixed Value

ProvidentFund = Basic * 0.12

Gratuity = Basic * .0481

OtherAllowance = (CTC - (Basic + HRA + ConveyanceAllowance + ProvidentFund + Gratuity))

我试过使用这里给出的解决方案。但是这个解决方案只有在所有计算值都是整数的情况下才有效，在我的情况下，这些值也可以包含十进制数字。我根据上述条件修改的代码如下：

public class PayStructure {

    public static void main(String[] args) {

        findAndprintSolutions(1, 1000000);

    }

    private static void findAndprintSolutions(int from, int to) {

        for (int a = from; a < to; a++) {

            for (int b = from; b < to; b++) {

                for (int c = from; c < to; c++) {

                    for (int d = from; d < to; d++) {

                        for (int e = from; e < to; e++) {

                            for (int f = from; f < to; f++) {

                                for (int g = from; g < to; g++) {

                                    if (isSolution(a, b, c, d, e, f, g))

                                        printSolution(new int[] { a, b, c, d, e, f, g });

                                }

                            }

                        }

                    }

                }

            }

        }

    }

    private static boolean isSolution(int a, int b, int c, int d, int e, int f, int g) {

        if (a != 100000)

            return false;

        if (b != a * (.4))

            return false;

        if (c != b / 2)

            return false;

        if (d != 10000)

            return false;

        if (e != b * (.12))

            return false;

        if (f != b * (.0481))

            return false;

        if (g != (a - (b + c + d + e + f)))

            return false;

        return true;

    }

此外，上述代码将被终止，因为 CTC 的最大值可能是数百万，并且根据变量的数量，时间复杂度最终会达到millions^NumberOfVariables. 是否有任何其他可能性来计算基于给定方程的值？方程和变量的数量可能会有所不同，但会有一个解决方案来计算每个变量的值，因此通用解决方案的任何输入都会更好。

Answer 1

也许您最好的选择是弄清楚如何将其转化为形式的线性方程组的形式c[1]x[1] + c[2]x[2] … + c[n]x[n] = 0。从那里，您可以使用广泛建立的线性系统技术来求解系统。有关大量信息，请参阅Wikipedia页面。您可以让用户以这种形式为您的方法提供输入，或者您可以对每个方程进行少量处理以对其进行转换（例如，如果所有方程在 LHS 上都有一个变量，如您的示例所示，则翻转签名并将其放在 RHS 的末尾）。解释求解线性方程组的理论超出了这个答案的范围，但基本上，如果有一个有效的分配，你的系统要么是唯一确定的，如果不存在有效的分配是过度确定的，或者如果有无限多的分配是可能的.&nbsp;如果有一个独特的任务，你会得到数字；如果系统未确定，您至少会得到一组约束，这些约束必须包含无限多个解决方案中的任何一个；如果不确定，您将一无所获并且知道原因。

Answer 2

使用 Java 的一些线性代数库。例如，使用此处记录的矩阵运算求解线性方程组。您的深层嵌套循环太慢了，有更好的算法可用。

Answer 3

这就是我解决这个问题的方法。首先，我通过将所有变量放在左侧并将值 & 0 放在右侧来创建方程：CTC = 1000000(0.4)CTC - Basic = 0(0.5)Basic-HRA = 0ConvAll = 10000(0.12)Basic-PF = 0(0.0481)Basic - Gratuity = 0CTC - (Basic + HRA + ConvAll + PF+ Gratuity + OtherAll) = 0然后我创建了一个这样的矩阵：|1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 0&nbsp; &nbsp; &nbsp;0&nbsp; &nbsp; 0&nbsp; &nbsp;0&nbsp; &nbsp;0&nbsp; &nbsp;0| |CTC&nbsp; &nbsp; &nbsp;| = |1000000||0.4&nbsp; &nbsp; &nbsp; &nbsp;-1&nbsp; &nbsp; &nbsp;0&nbsp; &nbsp; 0&nbsp; &nbsp;0&nbsp; &nbsp;0&nbsp; &nbsp;0| |Basic&nbsp; &nbsp;| = |0&nbsp; &nbsp; &nbsp; ||0&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;0.5&nbsp; &nbsp;-1&nbsp; &nbsp; 0&nbsp; &nbsp;0&nbsp; &nbsp;0&nbsp; &nbsp;0| |HRA&nbsp; &nbsp; &nbsp;| = |0|0&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 0&nbsp; &nbsp; &nbsp;0&nbsp; &nbsp; 1&nbsp; &nbsp;0&nbsp; &nbsp;0&nbsp; &nbsp;0| |ConvAll | = |10000&nbsp; ||0&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;0.12&nbsp; &nbsp;0&nbsp; &nbsp; 0&nbsp; -1&nbsp; &nbsp;0&nbsp; &nbsp;0| |PF&nbsp; &nbsp; &nbsp; | = |0&nbsp; &nbsp; &nbsp; ||0&nbsp; &nbsp; &nbsp; &nbsp; 0.0481&nbsp; 0&nbsp; &nbsp; 0&nbsp; &nbsp;0&nbsp; -1&nbsp; &nbsp;0| |Gratuity| = |10000&nbsp; ||1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;-1&nbsp; &nbsp; -1&nbsp; &nbsp;-1&nbsp; -1&nbsp; -1&nbsp; -1| |OtherAll| = |0&nbsp; &nbsp; &nbsp; |在此之后，我计算了（上面第一个矩阵的逆）和（最右边的矩阵）的乘积，并使用下面的代码得到了每个分量的相应值：public class Matrix{&nbsp; &nbsp; static int n = 0;&nbsp; &nbsp; public static void main(String argv[]) {&nbsp; &nbsp; &nbsp; &nbsp; Scanner input = new Scanner(System.in);&nbsp; &nbsp; &nbsp; &nbsp; System.out.println("Enter the dimension of square matrix: ");&nbsp; &nbsp; &nbsp; &nbsp; n = input.nextInt();&nbsp; &nbsp; &nbsp; &nbsp; double a[][] = new double[n][n];&nbsp; &nbsp; &nbsp; &nbsp; System.out.println("Enter the elements of matrix: ");&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 0; i < n; i++)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (int j = 0; j < n; j++)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; a[i][j] = input.nextDouble();&nbsp; &nbsp; &nbsp; &nbsp; double d[][] = invert(a);&nbsp; &nbsp; &nbsp; &nbsp; System.out.println();&nbsp; &nbsp; &nbsp; &nbsp; System.out.println("Enter the equation values: ");&nbsp; &nbsp; &nbsp; &nbsp; System.out.println();&nbsp; &nbsp; &nbsp; &nbsp; double b[][] = new double[n][1];&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 0; i < n; i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; b[i][0] = input.nextDouble();&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; double e[][] = multiplyMatrix(d, b);&nbsp; &nbsp; &nbsp; &nbsp; System.out.println();&nbsp; &nbsp; &nbsp; &nbsp; System.out.println("The final solution is: ");&nbsp; &nbsp; &nbsp; &nbsp; System.out.println();&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 0; i < n; i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (int j = 0; j < 1; j++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.printf(e[i][j] + " ");&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.println();&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; input.close();&nbsp; &nbsp; }&nbsp; &nbsp; public static double[][] invert(double a[][]) {&nbsp; &nbsp; &nbsp; &nbsp; int n = a.length;&nbsp; &nbsp; &nbsp; &nbsp; double x[][] = new double[n][n];&nbsp; &nbsp; &nbsp; &nbsp; double b[][] = new double[n][n];&nbsp; &nbsp; &nbsp; &nbsp; int index[] = new int[n];&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 0; i < n; ++i)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; b[i][i] = 1;&nbsp; &nbsp; &nbsp; &nbsp; // Transform the matrix into an upper triangle&nbsp; &nbsp; &nbsp; &nbsp; gaussian(a, index);&nbsp; &nbsp; &nbsp; &nbsp; // Update the matrix b[i][j] with the ratios stored&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 0; i < n - 1; ++i)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (int j = i + 1; j < n; ++j)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (int k = 0; k < n; ++k)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; b[index[j]][k] -= a[index[j]][i] * b[index[i]][k];&nbsp; &nbsp; &nbsp; &nbsp; // Perform backward substitutions&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 0; i < n; ++i) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; x[n - 1][i] = b[index[n - 1]][i] / a[index[n - 1]][n - 1];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (int j = n - 2; j >= 0; --j) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; x[j][i] = b[index[j]][i];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (int k = j + 1; k < n; ++k) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; x[j][i] -= a[index[j]][k] * x[k][i];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; x[j][i] /= a[index[j]][j];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return x;&nbsp; &nbsp; }&nbsp; &nbsp; // Method to carry out the partial-pivoting Gaussian&nbsp; &nbsp; // elimination. Here index[] stores pivoting order.&nbsp; &nbsp; public static void gaussian(double a[][], int index[]) {&nbsp; &nbsp; &nbsp; &nbsp; int n = index.length;&nbsp; &nbsp; &nbsp; &nbsp; double c[] = new double[n];&nbsp; &nbsp; &nbsp; &nbsp; // Initialize the index&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 0; i < n; ++i)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; index[i] = i;&nbsp; &nbsp; &nbsp; &nbsp; // Find the rescaling factors, one from each row&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 0; i < n; ++i) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; double c1 = 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (int j = 0; j < n; ++j) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; double c0 = Math.abs(a[i][j]);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (c0 > c1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; c1 = c0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; c[i] = c1;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; // Search the pivoting element from each column&nbsp; &nbsp; &nbsp; &nbsp; int k = 0;&nbsp; &nbsp; &nbsp; &nbsp; for (int j = 0; j < n - 1; ++j) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; double pi1 = 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (int i = j; i < n; ++i) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; double pi0 = Math.abs(a[index[i]][j]);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; pi0 /= c[index[i]];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (pi0 > pi1) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; pi1 = pi0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; k = i;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // Interchange rows according to the pivoting order&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int itmp = index[j];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; index[j] = index[k];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; index[k] = itmp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (int i = j + 1; i < n; ++i) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; double pj = a[index[i]][j] / a[index[j]][j];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // Record pivoting ratios below the diagonal&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; a[index[i]][j] = pj;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // Modify other elements accordingly&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (int l = j + 1; l < n; ++l)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; a[index[i]][l] -= pj * a[index[j]][l];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; public static double[][] multiplyMatrix(double a[][], double b[][]) {&nbsp; &nbsp; &nbsp; &nbsp; double c[][] = new double[n][1];&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 0; i < n; i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (int j = 0; j < 1; j++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (int k = 0; k < n; k++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; c[i][j] = c[i][j] + a[i][k] * b[k][j];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return c;&nbsp; &nbsp; }}谢谢大家的线索。