Заполните таблицу известными суммами строк и столбцов

Question

Я знаю значения сумм в строках и столбцах в матрице.Матрица мала (макс. 10x10) и значения находятся в диапазоне от 0 до 99.

Можно ли сгенерировать какую-либо матрицу из этих данных?Меня не интересуют все возможные комбинации.Только один будет в порядке.

Пример.

Task
              sum in columns     2   5   2
sum in rows    
     7                           ?   ?   ?
     0                           ?   ?   ?
     2                           ?   ?   ?

Answer

2   4   1
0   0   0
0   1   1 

Answer 1

Я не думаю, что это возможно, потому что есть более одного ответа. Например,

0 5 2
0 0 0
2 0 0

возвращает те же суммы строк и столбцов, что и матрица, которую вы указали.

Answer 2

int n, m;
int rows[n], cols[m];
int answer[n][m];

while (true) {
    boolean found = false;
    int row = -1, col = -1;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (rows[i] > 0 && cols[j] > 0 && (found == false || Math.min(rows[i], cols[j]) > Math.min(rows[row], cols[col])) {
                found = true;
                row = i;
                col = j;
            }
    if (!found)
        break;
    answer[row][col]++;
    rows[row]--;
    cols[col]--;
}

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

Answer 3

Если ответ существует, этот код найдет его:

int n, m;
int rows[n], cols[m];
int answer[n][m];

int n, m;
int rows[n], cols[m];
int answer[n][m];

for (int i = 0; i < n; i++) {
    int need = rows[i];
    for (int j = 0; need > 0 && j < m; j++) {
        int add = need;
        if (add > cols[j])
            add = cols[j];
        if (add > 99)
            add = 99;
        answer[i][j] = add;
        need -= add;
        cols[j] -= add;
    }
}