首页 新闻 论坛 群组 Blog 文档 下载 读书 Tag 网摘 搜索 .NET Java 游戏 视频 人才 外包 培训 数据库 书店 程序员
中国软件网
欢迎您:游客 | 登录 注册 帮助
    • 怎样求一个矩阵的最大子矩阵？ [已结贴,结贴人:hhz019]
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-04-27 23:52:20 楼主
      该矩阵的元素都是大于等于0，并且要求所求的最大子矩阵（该子矩阵的元素之和最大）不包含0；应该怎么做啊？
    大家讨论下看看有没什么好的算法。
    50  修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-04-28 03:57:301楼 得分:9
    初步的想法：
    构建一个子矩阵列表，记录子矩阵的起止范围，并初始化为原始矩阵；
    遍历矩阵，发现元素为 0 时：
        查找子矩阵列表，对包含该元素（位置）的子矩阵拆解为若干（2－4）个子矩阵，并放入子矩阵列表中；
        然后，消除子矩阵列表中被其他子矩阵包含的子矩阵。
    完成遍历，则所求的最大子矩阵必然为此子矩阵列表中的一个。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-04-28 12:09:042楼 得分:0
    是不是有点太复杂了。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-04-28 12:31:533楼 得分:0
    大家想想用动态规划怎么做啊？我一看到这道题就想用的动态规划，可是还没想出。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • dlyme
    • 等级:
    发表于：2008-04-28 14:03:314楼 得分:9
    这里说的子矩阵的行号和列号是不是连续的？
    如果是，那么可以动态规划，对于n*n的矩阵O(n^3)内能解决。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • dlyme
    • 等级:
    发表于：2008-04-28 14:30:545楼 得分:0
    设矩阵是m*n的，用a[i1][i2][j]表示第j列中从第i1行累加到第i2行的和(如果中间遇到0元素，那么最后的和直接置为0)，这里1 <=i1 <=i2 <=m，1 <=j <=n。
    对于每个a[i1][i2][1～n]序列，用动态规划的方法找这个序列中的最大连续子段和（复杂度O(n)），
    然后找出所有i1*i2序列（共有n*(n+1)/2个）中的最大值就可以了。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • dlyme
    • 等级:
    发表于：2008-04-28 14:31:556楼 得分:0
    然后找出所有i1*i2序列（共有n*(n+1)/2个）中的最大值就可以了。
    =>然后找出所有i1*i2序列（共有m*(m+1)/2个）中的最大值就可以了。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-04-28 17:20:077楼 得分:0
      开始没注意细看1楼大侠的做法，觉得蛮复杂的。后来自己也想了差不多的做法。先找到一个0的位置然后根据这个位置对矩阵进行分块，然后对分块矩阵继续分块直到分块矩阵里面没0（此时此子矩阵的和就是一个最大）。最后求出分块矩阵的最大值就行。不知道这个算法怎么样？
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-04-28 17:22:038楼 得分:0
      觉得dlyme的算法挺好的，学习学习。谢谢！
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-04-28 19:53:389楼 得分:8
    大王派我去巡山对0的处理有些问题哦。
    对于：
    1 0 2
    1 0 1
        +
    ------
    2 0 3
    接着调用最大字段和算法，
    那么得到的结果无疑是5。
    而根据作者的题意，这题的结果应该是3。

    不晓得我对你的0处理有没理解错，提出一点我的想法，哈哈。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-04-28 20:25:5810楼 得分:0
    我的想法是这样：
    设矩阵是m*n的，用a[i1][i2][j]表示第j列中从第i1行累加到第i2行的和(如果中间遇到0元素，那么最后的和直接置为0)，这里1 <=i1 <=i2 <=m，1 <=j <=n。
    对于每个a[i1][i2][1～n]序列(这个序列就是一个数组，设为B[1~n])执行下面的操作：
    1 扫描B[1~n]这个数组
    2 for i = 1 : n
      if B[i]!= 0
        total += B[i++]；
      else
      {
        if(total > sum)
            sum = total;
        total = 0;
      }
      end
    对所有m*(m+1)/2个）个序列都执行上面的数组操作即可找到最大的子矩阵。

    其实和大王叫我去巡山不同之处就在于不用最大字段和算法处理每个序列，而是用上面提到的直接扫描。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-04-28 22:17:4911楼 得分:8
    一般矩阵行数与列数不等。
    设置个标志数组：比如int l[m];c[n];//l[m]用来记录矩阵的第l[m]行是否有0；c[n]用来记录矩阵的第n列是否有0。扫描1遍矩阵就得到了。全部初始化为1；找到的有0行，相应的l[m]=0；最后数组元素为1的位置代表，最大子阵的行、列位置。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-01 07:12:1712楼 得分:8
    我也想了解，谢谢LZ.
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-01 08:45:0313楼 得分:8
    引用 4 楼 dlyme 的回复:
    这里说的子矩阵的行号和列号是不是连续的？
    如果是，那么可以动态规划，对于n*n的矩阵O(n^3)内能解决。
    修改 删除 举报 引用 回复
    网站简介－广告服务－网站地图－帮助－联系方式－诚聘英才－English－ 问题报告
    北京创新乐知广告有限公司 版权所有 京 ICP 证 070598 号
    世纪乐知(北京)网络技术有限公司 提供技术支持
    Copyright © 2000-2008, CSDN.NET, All Rights Reserved