Chinaunix首页 | 论坛 | 博客
  • 博客访问: 295090
  • 博文数量: 69
  • 博客积分: 2946
  • 博客等级: 少校
  • 技术积分: 800
  • 用 户 组: 普通用户
  • 注册时间: 2010-04-09 04:15
文章分类

全部博文(69)

文章存档

2013年(6)

2012年(16)

2011年(18)

2010年(29)

分类: C/C++

2010-08-02 23:46:25

问题描述:这个题目的意思很简单,有一个举证A[n][n],要从这个矩阵中找到一个子矩阵(至少为1×1),使得这个子矩阵的各项相加值最大。

从网上找了一下算法,用动态规划来做它是很确定的,参考了一位老兄的博客,写的很详细,也很容易理解,大家想看看可以点击上一行的“动态规划”,已经设置好链接。

这个题目首先要从一位的说起:

有 A1 A2 A3……An项,我们要求其一个字列,使得这个字列各项之和最大??


方法:1.遍历,计算出所有的可能性,这无疑是效率最低的一种方法,O(n^3)
    for(int i=0;i<n;i++)
    for(int j=i;j<n;j++)
    {
    int temp ;
    for(int k=i;k<=j;k++)
    temp =+ A[k];
    sum=sum>temp?sum:temp;
    }
    2.利用已有的计算结果可以减少一重for 循环,O(n^2)
    for(int i=0;i<n;i++) {
    int temp ;
    for(int j=i;j<n;j++)
    {
    temp=+A[j];
    sum=sum>temp?sum:temp;
    }
    }
    3.利用动态规划的处理,复杂度为O(n),空间复杂度也为O(n);
    int sum = -1000 , temp = 0;
    for(int i=0;i<n;i++)
    {
    if( temp >0) temp =+ A[i];
    else temp = A[i];
    sum=sum>temp?sum:temp;
    }

注意第三种方法,动态规划。因为在后面二维矩阵中将他推广一下。

    A11 A12 A13. . . . . . . . . A1n

    A21 A22 A23. . . . . . . . . .A2n
    . . . . . . . . . . . . . . .. . . . . .. . . .
    . . . . . . . . . . . . . . . . . . . . . . . .
    . . . . . . . . . . . . . . . . . . . . . . . .
    An1 An2 An3 . . . . . . . . . .Ann

上面是一个n*n的矩阵,现在要求它的最大子矩阵。

我们考虑这样一个数列[Ai1+..+Aj1 , Ai2+..+Aj2, Ai3..+Aj3 , Ai4..+ Aj4, .... , Ain...+ Ajn ],很熟悉。

上面这个数列的最大子序列便可以使用动态规划来求出。

到底有多少个这样的呢?? 这时我们关注一列,从第一列到第n列,一列n个数字[1,2,.......n] , 从中截取[i,...j];

    我们用两个for循环便可以解决截取的问题。最终程序代码贴在下面

    #include<iostream>
    #include<cstdlib>
    #define max 105
    int array[max][max];
    using namespace std ;
    int SubMax(int n,int* p)
    {
    int sum = -1000 ;
    int u = 0 ;
    for(int i=0;i<n;i++)
    {
    if(u<0) u = p[i];
    else u = p[i]+ u ;
    sum=u>sum?u:sum;
    }
    return sum ;
    }
    int main()
    {
    int number;
    int sum = -1000;
    cin>>number;
    if(number==1)
    {
    cin>>number;
    cout<<number<<endl;
    }
    else {
    for(int i=0;i<number;i++)
    for(int j=0;j<number;j++)
    cin>>array[i][j];
    int*point = new int[number];
    for(int i=0;i<number;i++)
    {
    for(int s=0;s<number;s++) //每次移动i后,对数组进行初始化

    point[s]=0;
    for(int j=i;j<number;j++)
    {
    for(int k=0;k<number;k++)
    point[k]=point[k]+array[j][k];
    int temp=SubMax(number,point);
    sum = sum>temp?sum:temp;
    }
    }
    cout<<sum <<endl;
    }
    system(“pause”);
    return 0 ;
    }


阅读(696) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~