2016-10-09

POJ-1050 To the Max

动态规划 —— 最大子矩阵和

问题描述：

给你一个N*N的矩阵，要求找出其一个子矩阵，使其各元素之和为最大。
原题地址: POJ-1050 To the Max

算法分析：

首先要学会最大子段和的求法(这道题的动态规划思想就体现在这里)

利用求最大子段和的算法， 将二维动态规划问题转化为一维动态规划问题
设一维数组b是二维数组a的i~j(0<=i<j<n)行，对应列元素的和，然后对数组b计算最大子段和。

构造最优解

参考代码：

计算最大子段和算法

/* besti, bestj 记录最大子段和的范围，用于构造最优解 */
int DP(int a[], int n, int& besti, int& bestj)
{
    int i;
    int max = -200000000;

    //当b[i-1]<=0时，记录b[i]=a[i]的位置
    int begin = 0;
    for(i = 1 ; i <= n ; i++ )
    {
        if (b > 0)
            b += a[i];
        else
        {
            b = a[i];
            begin = i;        //新的起始边界
        }
        if (b > max)
        {
            max = b;
            besti = begin;
            bestj = i;        //更新左右边界
        }
    }
    return max;
}

计算最大子矩阵和的动态规划算法

#define N 101
int main()
{
    int a[N][N];            // N*N矩阵 
    int sum[N];             // 一维数组 

    //构造最优解
    int rowI = 0;            //最大子矩阵的行号
    int rowJ = 0;            //最大子矩阵的行号
    int col = 0;             //最大子矩阵的列号

    int n;
    cin >> n;
    int i, j, k;
    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)
            cin >> a[i][j];

    int max = -128;
    for( i = 1 ; i <= n ; i++ )
    {
        memset(sum, 0, sizeof(sum));        //数组置零
        for(j = i ; j <= n ; j++ )
        {
            for( k = 1 ; k <= n ; k++ )
                sum[k] += a[j][k];    //取出第 i, j两行，将这两行之间的列对应相加，形成另外一个数组sum，对数组 sum求最大子段和
            int maxSum = DP(sum, n);
            if(maxSum > max)                //找出最大子矩阵和
            {
                rowI = i;
                rowJ = j;
                col = bestj;                //记录子矩阵的位置
                max = maxSum;
            }
        }
    }
    cout << max << endl;                    //输出最大子矩阵和

    /* 构造最优解: 打印出最大和的子矩阵 */
    for(i = rowI; i <= rowJ; i++)
    {
        for(j = 1; j <= col; j++)
        {
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

可以将以上代码简化

#define N 101
int main()
{
    int a[N][N];        // N*N矩阵 
    int b[N];             // 一维数组 

    //构造最优解
    int rowI = 0;        //最大子矩阵的行号
    int rowJ = 0;        //最大子矩阵的行号
    int col = 0;         //最大子矩阵的列号

    int n;
    cin >> n;

    int max = -128;
    for( i = 1; i <= n; i++ )
    {
        memset(b, 0, sizeof(b));        //数组置零
        for(j = i; j <= n; j++ )
        {
            //下面是针对数组b求最大子段和的算法 
            int sum = 0; 
            for( k = 1; k <= n; k++ )
            {
                b[k] += a[j][k];
                sum += b[k];
                if(sum < b[k]) sum = b[k];
                if(sum > max)                //找出最大子矩阵和
                {
                    rowI = i;
                    rowJ = j;
                    col = bestj;            //记录子矩阵的位置
                    max = sum;
                }
            }

        }
    }
    cout << max << endl;                    //输出最大子矩阵和

    return 0;
}