⑴ 给出一个矩阵，求子矩阵中各元素和最大的子矩阵，求算法。
双层ST算法。
⑵ python的矩阵可以做什么
python的numpy库提供矩阵运算的功能，因此我们在需要矩阵运算的时候，需要导入numpy的包。
计算矩阵对应行列的最大、最小值、和。
3>>>a1=mat([[1,1],[2,3],[4,2]])
>>> a1
matrix([[1, 1],
[2, 3],
[4, 2]])
计算每一列、行的和
>>>a2=a1.sum(axis=0) #列和，这里得到的是1*2的矩阵
>>> a2
matrix([[7, 6]])
>>>a3=a1.sum(axis=1) #行和，这里得到的是3*1的矩阵
>>> a3
matrix([[2],
[5],
[6]])
>>>a4=sum(a1[1,:]) #计算第一行所有列的和，这里得到的是一个数值
>>> a4
5 #第0行：1+1；第2行：2+3；第3行：4+2
计算最大、最小值和索引
>>>a1.max() #计算a1矩阵中所有元素的最大值,这里得到的结果是一个数值
4
>>>a2=max(a1[:,1]) #计算第二列的最大值，这里得到的是一个1*1的矩阵
>>> a2
matrix([[3]])
>>>a1[1,:].max() #计算第二行的最大值，这里得到的是一个一个数值
3
>>>np.max(a1,0) #计算所有列的最大值，这里使用的是numpy中的max函数
matrix([[4, 3]])
>>>np.max(a1,1) #计算所有行的最大值，这里得到是一个矩阵
matrix([[1],
[3],
[4]])
>>>np.argmax(a1,0) #计算所有列的最大值对应在该列中的索引
matrix([[2, 1]])
>>>np.argmax(a1[1,:]) #计算第二行中最大值对应在该行的索引
1
⑶ python:二维数组中每行最大值和每行和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def get_max_value(martix):
'''
得到矩阵中每一列最大的值
'''
res_list=[]
for j in range(len(martix[0])):
one_list=[]
for i in range(len(martix)):
one_list.append(int(martix[i][j]))
res_list.append(str(max(one_list)))
return res_list
if name == 'main':
martix=[['1','2','3'],['3','5','0'],['5','6','2']]
print get_max_value(martix)
结果如下：
['5', '6', '3']
⑷ [python] 2019-03-09
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0
假设矩阵m的大小为M*N，行数为M，列数为N。生成大小和m
一样的矩阵dp，行数为M，列数为N，dp[i][j]的值表示从左上角，也就是（0，0）位置走到（i，j）位置的最小路径和。
dp[i][j]=m[i][j]+min{dp[i-1][j], dp[i][j-1]}
arr：2 1 5 3 6 4 8 9 7
dp： 1 1 2 2 3 3 4 5 4
dp[i]表示在必须以arr[i]这个数结尾的情况下，arr[0,…i]中的最大递增子序列的长度。
dp[i]=max{dp[j]+1(0<=j<i, arr[j]<arr[i])}
假设str1的长度为M，str2的长度为N，生成大小为M*N的矩阵dp。dp[i][j]的含义是str1[0...i]与str2[0...j]的最长公共子序列的长度。
dp求法如下：
三个最大的值，取一个即可。
假设物品编号从 1 到 n，一件一件物品考虑是否加入背包。
假设 dp[x][y] 表示前 x 件物品，在不超过重量 y 的时候的最大价值。枚举一下第 x 件物品的情况：
情况一：如果选第 x 件物品，则前 x - 1 件物品得到的重量不能超过 y - w[x]。
情况二：如果不选 x 件物品，则前 x - 1 件物品得到的重量不能超过 y。
无论哪种情况，我们都需要去求解 x - 1 件物品的情况。
所以，dp[x][y] 可能等于 dp[x-1][y]，也就是不取第 x 件物品的时候，价值和之前的一样。
也可能是 dp[x-1][y - w[x]] + v[x]，也就是决定拿第 x 件物品的情况，当然会加上 x 物品的价值。
两种可能性中，应该选择价值最大的那个，状态转移方程如下：
dp[x][y] = Max{dp[x-1][y], dp[x-1][y-w[x]]+v[x]}
对于 dp 矩阵来说，行数是物品的数量 n，列数是背包的最大承重 w。然后再从左到右，从上到下计算所有的 dp 的值即可。
该矩阵中的每个值的求解都代表一个更小的背包问题。
初始情况一：对于第0列，它的含义是背包的容量为0。此时物品的价值呢？没有。因此，第一列都填入0。
初始情况二：对于第0行，它的含义是屋内没有物品。那么没有任何物品的背包里的价值多少呢？还是没有！所有都是0。
所以我们可以把这个矩阵的大小定义为 dp[n+1][y+1]，从第二行第二列也就是 dp[1][1] 的位置开始带入状态转移方程进行计算，其实这也解决了我长期以来对这个矩阵的行列都+1的困扰。
解题方法：
动态规划。首先生成大小为(M+1)X(N+1)的矩阵dp。
假设str1="av=b12cd3", str2="abcdf"。dp[i][j]表示str1[0:i]编辑成str2[0:j]的最小代价。计算结果如下：
计算步骤：
1、dp[0][0]表示str1空的子串编辑成str2空的子串的代价为0
2、矩阵dp第一列即dp[0:M-1][0], dp[i][0] 表示str1[0:i-1]编辑成空串的最小代价，即把str1[0:i-1]中所有字符删掉的代价，所以dp[i][0] = dc * i
3、矩阵第一行即dp[0][0:N-1], dp[0][j]表示空串编辑成str2[0:j-1]的最小代价，即向空串中添加字符的代价，所以dp[0][j] = ic * j
4、其他位置，从左到右，从上到下计算，dp[i][j]的值可能来自于一下四种情况：
（1）str1[0:i-1]先编辑成str1[0:i-2]，即先删除字符str1[i]，然后由str1[0:i-2]编辑成str2[0:j-1],dp[i-1][j] 表示str1[0:i-2]编辑成石头人[0:j-1]的最小代价，那么dp[i][j]可能等于dc + dp[i-1][j]
（2）str1[0:i-1]可以先编辑成str2[0:j-2],然后向str2[0:j-2]插入字符str2[j-1],编辑成str2[0:j-1]，dp[i][j-1]表示str1[0:i-1]编辑成str2[0:j-2]的最小代价，那么dp[i][[j]可能等于dp[i][j-1] + ic;
(3) 如果str1[i-1] != str2[j-1], 可以先将str1[0:i-2]编辑成str2[0:j-2],然后将str1[i-1]替换成str2[j-1]，dp[i-1][j-1]表示将str1[0:i-2]编辑成str2[0:j-2]的最小代价，那么dp[i][j]可能等于dp[i-1][j-1]+rc
（4）如果str1[i-1] == str2[j-1], 则此时dp[i][j] = dp[i-1][j-1]
以上四种可能的值中，选最小值作为dp[i][j]的值。
⑸ 用C语言编程，要求求出最大子矩阵和，且复杂度为O(N^4) ,穷举的O(N^6)和动态规划的O(N^3)就不用来了。
主要思想就是把2维德矩阵压缩为1维
然后把问题转化为：给你一个长度确定的序列，要你在这个序列里求一个权值最大的连续子区间
这个你会不？
也就是说，举个例子
1 -1 2 0 3 5 8
2 7 3 1 -9 -8 1
对于这个矩阵
我们求出的子矩阵只要求权值和最大，那么那个最优解必然是
第一排的连续K个数之和加第二排连续K个数之和
即a[1][i]+a[1][i+1]+....a[1][i+k] + a[2][i]+...a[2][i+k];
也等于 a[1][i]+a[2][i]+a[1][i+1]+a[2][i+1].....
也就是相当于如果把第二排和第一排相加，变成一排数，那么这一排数就是一个宽度为2的矩阵
那么问题就转化为在序列 C1,C2,C3...Cn中求出一个最大的连续子区间。，那么求出的这个区间还原的话就是一个K*2的矩阵。
通过这个方法，我们可以枚举所有的排数，即找一个起点排，找一个终点排，把这之间的的所有数压缩为一行，然后压缩后的序列用动态规划求一次最大连续子区间。
整个问题也就解决了
对于求最长连续子区间
我们设F[i]为序列C的前i个数，必须以i作为结尾的最长连续子区间。
因为是连续区间，所以说对于第i个数只有两种决策，要么和前面的数连在一起，要么自己作为开头。
那么F[I]=MAX(F[I-1]+C[I],C[I])
/*
ID: englanq1
PROG:
LANG: C++
*/
#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
int map[200][200];
int f[200];
int n,ans;
int a[200];
void readdata()
{
scanf("%d\n",&n);
int i,j;
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
scanf("%d",&map[i][j]);
}
void work()
{
int i,j,q,tem,m,k;
for(i=1; i<=n; i++)
for(j=1; j<=n-i+1; j++)
{
for(q=1; q<=n; q++)
{
tem=0;
for(k=i; k<=i+j-1; k++)
tem+=map[k][q];
a[q]=tem;
}
for(q=0; q<=n; q++)
f[q]=0;
f[1]=a[1];
if(f[1]>ans) ans=f[1];
for(m=2; m<=n; m++)
{
f[m]=a[m]>f[m-1]+a[m] ? a[m]:f[m-1]+a[m];
if(f[m]>ans) ans=f[m];
}
}
}
void print()
{
printf("%d\n",ans);
}
int main()
{
readdata();
work();
print();
return 0;
}
⑹ 怎样求一个矩阵中和最大的子区域
ACM accepted code
#include<stdio.h>
int matrix[1000][1000];
int main()
{
int n,max1,max2=-1000000;
int i,j,k,h1,h;
scanf("%d",&n);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&matrix[i][j]);
for(i=0;i<n;i++)
for(k=i;k<n;k++)
{
max1=0;
for(h1=0;h1<n;h1++)
{
for(h=i;h<=k;h++) max1+=matrix[h1][h];
if(max1>max2) max2=max1;
if(max1<0) max1=0;
}
}
printf("%d\n",max2);
return 0;
}
⑺ python如何申请超大二维矩阵
我试着跑了一下，也是报内存错误，原因就是内存不够，你可以试试使用numpy模块看看，然后运行numpy.zeros((43373 x 43373))，查看是否会报错array is too big，如果是这样说明你内存不够