给定Nx2矩阵中第一行和最后一行的总和以及所有列的总和，求出矩阵(C++)中每个单元格的值

Question

我目前正在准备面试考试(试图找到我的第一份工作(。我很难找到这个问题的算法。我很想得到一些帮助：

给定第一行和最后一行的总和，以及一个具有Nx2矩阵中所有列的总和的数组，求出矩阵中每个单元格的值，其中每个单元格为0或1。

提前感谢！

Answer 1

我假设要重新创建的矩阵是2xN，而不是Nx2。那么你就有了找到问题答案所必需的全部金额。

天真的算法是递归的，有随机选择和条件检查。迭代第n列的两个单元格的所有可能组合，如果没有一个通过行和检查(当前和高于预期和(，则返回一列测试下一个组合的n-1列。否则，使用第n列上经过的第一个组合移动到n+1。这将只找到一个解决方案，如果它存在

在伪代码中，递归方法看起来像：

def find_combination_for_column(n):
if n > max_n return 0
for each x, y in possible_combination(n)
if n == max_n and curr_sum_1 + x == expected_1 and curr_sum_2 + y == expected_2
// result foud here, print and exit
print(x, y)
return 1
if curr_sum_1 + x > expected_1 or curr_sum_2 + y > expected_2
// go back to previous column
return 0
if find_combination_for_column(n + 1)
// result already found, all that's left is to print this column's parameters and continue exiting
print(x, y)
return 1
// else go to next combination

编辑

没有看到唯一可能的值在0和1之间。不过，这种天真的方法应该仍然有效，但您可以跳过总和为0或2的列，因为只有一个组合是可能的。

Answer 2

答案是不可能有答案：让我用下面的例子来证明这一点：找到一个4x4矩阵，其中每个单元格值都是0或1，每行和每列的和等于2。有以下解决方案：

1 0 1 0
0 1 0 1
1 0 1 0
0 1 0 1
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0
1 1 0 0
1 1 0 0
0 0 1 1
0 0 1 1
0 0 1 1
0 0 1 1
1 1 0 0
1 1 0 0
1 0 0 1
0 1 1 0
0 1 1 0
1 0 0 1
... (there are lots and lots of solutions)

我相信这次面试的真正问题是：你能确定一个问题是无法解决的吗？

Answer 3

我假设您有N行2列，以及每行和每列的总和。

不需要回溯，在线性时间内找到解决方案是可行的(实际上通常有不止一个解决方案(。如果有解决方案，你会找到的。否则，你可以确定它。

在伪代码中：

rows_with_choice = []
sum_so_far = 0
# Fill all rows for which there is no choice
for i in range(N):
# If the sum is 0, each element is 0. If the sum is 2, they are both 1.
if sum_row(i) in [0; 2] : 
M[i][0] = sum_row(i) / 2
M[i][1] = sum_row(i) / 2
sum_so_far += sum_row(i)
else:
rows_with_choice.append(i)   # These are the indices of the rows that contain either (0; 1) or (1; 0)
already_in_each_col = sum_so_far / 2  # Each column already has that number of 1s.
if already_in_each_col > min(sum_col):
print('No solution exists')
return
if len(rows_with_choice) + sum_so_far != sum_col[0] + sum_col[1]:
print('No solution exists')
return
# Among the rows that have a choice, fill the correct amount as (1; 0) and the rest as (0; 1)
for j in range(sum_col(0) - already_in_each_col):
i = rows_with_choice[j]
M[i][0] = 1
M[i][1] = 0
for j in range(sum_col(1) - already_in_each_col):
i = rows_with_choice[j + sum_col(0) - already_in_each_col] 
M[i][0] = 0
M[i][1] = 1