⑴ 給出一個矩陣，求子矩陣中各元素和最大的子矩陣，求演算法。
雙層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，如果是這樣說明你內存不夠