30行20列矩阵,在20列中每一列取一个数,每个数不同行,求和最小
时间: 2023-05-19 19:01:17 浏览: 91
这是一个经典的线性规划问题,可以使用贪心算法来解决。首先将每一列按照从小到大的顺序排序,然后从第一列开始,依次选择每一列中最小的数,直到选满20个数为止。这样可以保证每个数不同行,并且求和最小。具体实现可以参考以下代码:
```python
import numpy as np
# 生成随机矩阵
matrix = np.random.randint(0, 100, size=(30, 20))
# 对每一列进行排序
sorted_matrix = np.sort(matrix, axis=0)
# 依次选择每一列中最小的数
selected_nums = []
for i in range(20):
min_num = sorted_matrix[0][i]
min_row = 0
for j in range(1, 30):
if sorted_matrix[j][i] < min_num:
min_num = sorted_matrix[j][i]
min_row = j
selected_nums.append(min_num)
sorted_matrix = np.delete(sorted_matrix, min_row, axis=0)
# 求和
sum = np.sum(selected_nums)
print(sum)
```
输出结果为选出的20个数的和。
相关问题
30行20列矩阵,在20列中每一列取一个数,每个数不同行,求和最小,并输出每个值的取法
这是一个经典的线性规划问题,可以使用匈牙利算法来解决。以下是一个简单的 Python 代码实现:
```python
import numpy as np
from scipy.optimize import linear_sum_assignment
# 构造随机矩阵
matrix = np.random.rand(30, 20)
# 使用匈牙利算法求解
row_ind, col_ind = linear_sum_assignment(matrix)
# 输出结果
print("每个值的取法:")
for i in range(len(row_ind)):
print("第 %d 列取第 %d 行的值" % (col_ind[i], row_ind[i]))
print("求和最小值为:", matrix[row_ind, col_ind].sum())
```
输出结果类似于:
```
每个值的取法:
第 0 列取第 7 行的值
第 1 列取第 6 行的值
第 2 列取第 23 行的值
...
求和最小值为: 5.175
```
注意,这个算法只能保证求得的解是最优解之一,不一定是唯一的最优解。
4*4的矩阵每一行取一个求和每一列只能用一次用matlb
这个问题可以使用回溯法进行求解,MATLAB中可以使用递归函数实现回溯法。下面是MATLAB的代码实现:
```matlab
function result = sum_matrix(matrix)
% matrix为输入的4*4矩阵
col_selected = zeros(1, 4);
result = backtrack(1, [], 0, col_selected, matrix);
end
function res = backtrack(row_idx, row_selected, row_sum, col_selected, matrix)
if row_idx > 4
if all(col_selected)
res = row_sum;
else
res = NaN;
end
else
res = NaN;
for i = 1:4
if ~ismember(i, row_selected)
new_row_sel = [row_selected, i];
new_row_sum = row_sum + matrix(row_idx, i);
if new_row_sum >= res
continue;
end
new_col_sel = col_selected;
new_col_sel(i) = 1;
res_ = backtrack(row_idx+1, new_row_sel, new_row_sum, new_col_sel, matrix);
if isnan(res)
res = res_;
elseif ~isnan(res_) && res_ < res
res = res_;
end
end
end
end
end
```
首先定义一个`sum_matrix`函数,输入为一个4*4的矩阵,输出为矩阵每行取一个时的最小和。
然后定义一个递归函数`backtrack`,其中`row_idx`表示当前选择的行数,`row_selected`表示已经选择的行数,`row_sum`表示已经选择的行的和,`col_selected`表示每列是否被选择,`matrix`为输入的矩阵。
在递归函数中,首先判断是否已经选择完所有行,如果是,则判断每列是否都被选择,如果是,则返回当前行的和,否则返回NaN表示无解。
如果还没有选择完所有行,则对于每一行,从中选择一个数,并将其加入到已选取的列表中,同时更新当前选取的行的和。如果当前选取的行的和已经大于等于之前找到的解,则表示当前路径不可行,回溯到上一行重新选择。如果遍历完整个矩阵仍未找到解,则返回 NaN。
最终在`sum_matrix`函数中调用`backtrack`函数,得到矩阵每行取一个时的最小和。