algorithm - 为什么这个算法总是有效？使矩阵的每一行和每一列都相等所需的最少操作

Question

给定一个大小为 n x n 的方阵。查找最小操作数是必需的，使得每行和每列的元素之和变得相等。在一个操作中，将矩阵单元格的任何值递增 1。在第一行打印所需的最小操作，在接下来的“n”行中打印代表操作后最终矩阵的“n”个整数。

输入:

1 2
3 4

输出:

4
4 3
3 4

解释

1. 将 cell(0, 0) 的值增加 3
2. 将 cell(0, 1) 的值增加 1因此总共需要4个操作

输入:9

1 2 3
4 2 3
3 2 1

输出:

6
2 4 3
4 2 3
3 3 3

解决方案说明:

方法很简单，我们假设 maxSum 是所有行和列的最大总和。我们只需要增加一些单元格，使任何行或列的总和变为“maxSum”。假设 Xi 是使“i”行的总和等于 maxSum 所需的操作总数，Yj 是使“j”列的总和等于 maxSum 所需的操作总数。由于 Xi = Yj 所以我们需要根据条件在其中任何一个上工作。

为了最小化 Xi，我们需要从 rowSumi 和 colSumj 中选择最大值，因为它肯定会导致最小操作。之后根据递增后满足的条件递增'i'或'j'。

下面是上述方法的实现。

解决方案代码:

// Java Program to Find minimum 
// number of operation required 
// such that sum of elements on 
// each row and column becomes same
import java.io.*;

class GFG {

// Function to find minimum
// operation required
// to make sum of each row
// and column equals
static int findMinOpeartion(int matrix[][],
                                     int n)
{
    // Initialize the sumRow[]
    // and sumCol[] array to 0
    int[] sumRow = new int[n];
    int[] sumCol = new int[n];

    // Calculate sumRow[] and
    // sumCol[] array
    for (int i = 0; i < n; ++i)

        for (int j = 0; j < n; ++j)
        {
            sumRow[i] += matrix[i][j];
            sumCol[j] += matrix[i][j];
        }

    // Find maximum sum value 
    // in either row or in column
    int maxSum = 0;
    for (int i = 0; i < n; ++i) 
    {
        maxSum = Math.max(maxSum, sumRow[i]);
        maxSum = Math.max(maxSum, sumCol[i]);
    }

    int count = 0;
    for (int i = 0, j = 0; i < n && j < n;) 
    {
        // Find minimum increment
        // required in either row
        // or column
        int diff = Math.min(maxSum - sumRow[i],
                    maxSum - sumCol[j]);

        // Add difference in 
        // corresponding cell,
        // sumRow[] and sumCol[]
        // array
        matrix[i][j] += diff;
        sumRow[i] += diff;
        sumCol[j] += diff;

        // Update the count 
        // variable
        count += diff;

        // If ith row satisfied,
        // increment ith value 
        // for next iteration
        if (sumRow[i] == maxSum)
            ++i;

        // If jth column satisfied, 
        // increment jth value for
        // next iteration
        if (sumCol[j] == maxSum)
            ++j;
    }
    return count;
}

// Utility function to 
// print matrix
static void printMatrix(int matrix[][],
                                 int n)
{
    for (int i = 0; i < n; ++i) 
    {
        for (int j = 0; j < n; ++j)
            System.out.print(matrix[i][j] +
                                       " ");

        System.out.println();
    }
}

/* Driver program */
public static void main(String[] args)
{
    int matrix[][] = {{1, 2},
                      {3, 4}};

    System.out.println(findMinOpeartion(matrix, 2));
    printMatrix(matrix, 2);

}
}

// This code is contributed by Gitanjali.

我的问题:

我不明白为什么这段代码适用于所有情况。这对我来说并不明显，为什么要解决这个问题我可以从矩阵的左上角开始并贪婪地解决整个问题，而不检查如果我从其他位置开始会发生什么，例如左下角或右上角。当我从不同的起始位置解决一些例子时，我会得到一个不同的矩阵，但在行和列的相等性方面是正确的，但对我来说为什么会发生这种情况有点神奇。任何建议表示赞赏!

Answer 1

这个问题可以表述如下。

假设我们有n个人在摘草莓，还有n个篮子。我们的目标是每人摘取相同的号码，每个篮子的号码相同(多摘草莓的数量最少。

矩阵A[i,j]表示第i个人放入篮子j中的草莓数量。

我们的想法是，我们可以通过简单地要求任何仍有工作要做的人将草莓放入任何未满的篮子中来实现这一目标。

即只要他们还有空间，选择哪个人或哪个篮子都没有关系。在给定的算法中选择的顺序可以很容易地跟踪哪些人和篮子有空间。