程序员经验分享-hwhale

求矩阵中不同行和列的元素总和的最大值

2024-01-12

我有一个 nxm 矩阵，我需要找到不同行和列中其值之和的最大值。

例如考虑以下矩阵：

      m1 m2 m3
n1    1  2  3
n2    4  5  6
n3    7  8  9
n4    10 11 12

最大值为 12+8+4 = 24

请注意，查找最大值并消除属于该列或行的所有值并不是一个好的解决方案，因为它并不适用于所有情况。

上述例外情况如下：

     m1  m2
n1   17  1
n2   18  15

如果找到 18，去掉 17 和 15，总和就是 18+1 = 19。而 17+15 = 32 的值更高。

对这个问题的算法有什么想法吗？


解决方案是使用匈牙利算法。这是一个复杂的算法。 youtube 上有一个非常好的讲座：

http://www.youtube.com/watch?v=BUGIhEecipE http://www.youtube.com/watch?v=BUGIhEecipE

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Algorithm

matrix

Sum

max

Distinct

求矩阵中不同行和列的元素总和的最大值 的相关文章

  • 通过分布式数据库聚合作业优化网络带宽

    我有一个分布式 联合数据库 结构如下 数据库分布在三个地理位置 节点 每个节点集群有多个数据库 关系数据库是 PostgreSQL MySQL Oracle 和 MS SQL Server 的混合体 非关系数据库是 MongoDB 或 Ca

  • 检索受“rowspan”影响的行的列索引的最有效方法是什么？

    考虑下表 table thead tr th th th A th th B th th C th tr thead tbody tr th 1 th td Apples td td Oranges td td Pears td tr tb

  • 如何将无向图转换为 DAG？

    The 维基页面 http en wikipedia org wiki Directed acyclic graph Relation to other kinds of graphs says 任何无向图都可以通过为其顶点选择总顺序并将每

  • 高维最近邻搜索的最佳数据结构

    我实际上正在处理高维数据 50 000 100 000 个特征 并且必须对其执行最近邻搜索 我知道随着维度的增长 KD 树的性能很差 而且我还了解到 一般来说 所有空间分区数据结构都倾向于对高维数据执行详尽的搜索 此外 还有两个重要事实需要

  • 固定大小集以包含给定集的最大数量

    我有大约 1000 组尺寸 1 4 1 3 3 5 6 4 5 6 7 5 25 42 67 100 是否有可能找到包含最大数量的给定集合的大小为 20 的集合 检查每一个100 80 20 集 效率低下 我不太确定这是 NP 完全的 考虑

  • 如何确定算法函数的复杂度？

    您如何知道算法函数对于特定操作是否需要线性 常数 对数时间 它取决于CPU周期吗 您可以通过三种方式 至少 做到这一点 在网上查找算法 看看它是如何描述其时间复杂度的 根据输入大小 自己检查算法 查看嵌套循环和递归条件等内容 以及每个循环运

  • 选择一个单元格内的最小值或最大值（分隔字符串）

    我有一个数据框 其中每个样本的列可以有多个值 例如 Gene Pvalue1 Pvalue2 Pvalue3 Beta Ace 0 0381 0 00357 0 01755 0 001385 0 0037 NA 0 039 0 03 1 1

  • 再现频率矩阵图

    我想在 R 中重新创建一个情节 情节如下 来源 Boring E G 1941 作为动态平衡的统计频率 心理学评论 48 4 279 这略高于我的工资等级 能力 因此在这里询问 无聊的状态 第一次 A 只能出现 从不 0 或 总是 1 在

  • 将字符串中的“奇怪”字符转换为罗马字符

    我需要能够将用户输入仅转换为 a z 罗马字符 不区分大小写 所以 我感兴趣的角色只有26个 然而 用户可以输入他们想要的任何 形式 的字符 西班牙语 n 法语 e 和德语 u 都可以包含用户输入中的重音符号 这些重音符号会被程序删除 我已

  • 在常数空间中创建 1..N 的随机排列

    我正在寻找枚举固定空间中数字 1 N 的随机排列 这意味着我无法将所有数字存储在列表中 原因是 N 可能非常大 超过可用内存 我仍然希望能够一次遍历这样一个数字的排列 只访问每个数字一次 我知道对于某些 N 可以这样做 许多随机数生成器随机

  • Python 将列表追加到列表中

    我正在尝试编写一个通过矩阵的函数 当满足条件时 它会记住该位置 我从一个空列表开始 locations 当函数遍历行时 我使用以下方法附加坐标 locations append x locations append y 函数末尾的列表如下所

  • 如何检查是否存在可能的路径？

    我正在开发一个基于 javascript 的实验性游戏 玩家必须在二维平铺地图上移动才能退出 请随意检查这个小提琴并演奏 http jsfiddle net moonlife 74vLd 我只是随机放置障碍物 但有时障碍物会挡住玩家和出口之

  • shell脚本中关联数组的时间复杂度

    我想知道在 shell 脚本中使用关联数组时如何构造 实现 另外 我想知道基于 shell 脚本的关联数组的时间复杂度是否是最佳的 因为我们可以使用字母和数字作为它们各自的键 编辑 他们使用什么哈希函数 如果您使用关联数组 则不能通过 使用

  • 子序列和

    给定一个整数数组 例如 1 2 3 1 查找是否存在总和为0并返回它 例如 1 2 3 or 2 3 1 检查每个子序列是O n 2 这效率太低了 有改进的想法吗 创建一个新数组 其中每个元素等于前一个元素加上该元素的总和 Input 1

  • 找到一条穿过任意节点序列的最短路径？

    In 这个先前的问题 https stackoverflow com questions 7314333 find shortest path from vertex u to v passing through a vertex wOP询

  • 具有 2 个属性的背包算法。如何在 3d 数组中实现它？

    当有超过 1 个属性时 我无法理解背包问题 当有 1 个属性时 我必须编写一个使用具有 2 个属性的背包算法的程序 老师告诉我们 它必须在 3d 数组中完成 错误的实现将导致 O 2 n 处理时间 我无法想象这样的数组会是什么样子 假设这是

  • numpy python 中的“AttributeError：'matrix'对象没有属性'strftime'”错误

    我有一个维度为 72000 1 的矩阵 该矩阵涉及时间戳 我想使用 strftime 如下所示 strftime d m y 为了得到像这样的输出 11 03 02 我有这样一个矩阵 M np matrix timestamps 我使用了

  • 从一种数字系统转换为另一种数字系统后会有多少位数字

    主要问题 有多少位数字 让我解释 我有一个二进制数 11000000 十进制数是192 转换为十进制后 它有多少位 以十进制表示 在我的示例中 它是 3 位数字 但是 这不是问题 我在互联网上搜索并找到了一种用于整数部分的算法和一种用于小数

  • Florian 的 Grisu2 算法如何工作？

    我遇到了一个关于将 double 转换为 ascii 的问题 经过搜索 我得到了 Florian 的论文 使用整数快速准确地打印浮点数 http www cs tufts edu nr cs257 archive florian loits

  • 大数据使用什么数据结构

    我有一个包含一百万行的 Excel 工作表 每行有 100 列 每行代表一个具有 100 个属性的类的实例 列值是这些属性的值 哪种数据结构最适合在这里使用来存储数百万个数据实例 Thanks 这实际上取决于您需要如何访问这些数据以及您想要

随机推荐

  • 如果批量使用GTR/LSS运算符

    我有一个越来越大的批处理文件 它使用GTR LSS运营商 问题是if语句只允许我输入某些值 在以下示例中 输入值 2 3 或 4 将返回 值太高 char intb set char points 30 set a limit char p

  • wsdl2java - 警告：无法初始化默认密钥管理器

    在生成 java WSDL 客户端时 我收到这些错误 你能帮我理解这些吗 C Users Administrator workspace apache cxf 3 0 2 bin gt wsdl2javahttps example com

  • 使用 TF-IDF 分数进行文本分类的 KNN

    我有一个 CSV 文件 corpus csv 其中包含语料库中以下格式的分级摘要 文本 Institute Score Abstract UoM 3 0 Hello this is abstract one UoM 3 2 Hello th

  • Android studio 防止粘贴时代码重新格式化[重复]

    这个问题在这里已经有答案了 我已经开始使用 Android Studio 取代 Eclipse 但我无法习惯的一件事是 Studio 如何自动 在某些情况下 重新格式化当前文件中的部分甚至全部代码 其中一种情况是将文本粘贴到我的文件中 当我

  • 正则表达式：+$ VS *$ VS 无

    在正则表达式中 有什么区别 a zA Z and a zA Z 我也可以根本不包括它吗 a zA Z or a zA Z 我在网上查了一下 上面写着 匹配前面的字符一次或多次并且 匹配前面的字符零次或一次 但我不知道这在这种情况下意味着什么

  • 删除按钮处于活动状态（单击）时的阴影

    我有这个 CSS 用于按钮动画和其他 btnliner background url images btnbg png no repeat center 105px Fallback display block text align cen

  • 如何用C#模拟浏览器HTTP POST请求并捕获结果

    假设我们有一个带有搜索输入表单的网页 它通过 HTTP GET 将数据提交到服务器 这意味着服务器通过查询字符串接收搜索数据 用户可以看到 URL 也可以自己初始化此请求 通过 URL 查询字符串 我们都知道 这是问题所在 如果这个网页通过

  • Javascript：显示带有复选框值的图像

    我目前正在使用单选按钮和复选框来在 javascript 的帮助下显示图像 具体来说 我在处理复选框和显示图像时遇到问题 使用单选按钮时 只会显示该类别的一张图像 但对于复选框 需要显示多个图像 例如 用户可以检查夹克和手套的字段 并且将显

  • 如何在node.js中使用CasperJS？

    我想在node js 中使用CasperJS 我参考了以下 URL 在 node js 中使用 CasperJS https github com sgentle phantomjs node https github com sgentl

  • Angular Js：类属性指令中的 onchange 不起作用

    控制指令 js function validVehicleyear scope http return restrict C scope ngModel link function scope element attrs ngModel e

  • 在 Docker 中启动并填充 Postgres 容器

    我有一个包含 Postgres 数据库的 Docker 容器 这是用官方的Postgres 图像 https registry hub docker com postgres 其中有一个 CMD 条目在主线程上启动服务器 我想通过运行来填充

  • xcode 8 错误被服务委托拒绝 (SBMainWorkspace)

    尝试在模拟器上运行构建 我收到此错误 打开 com companyname appname 的请求失败 请求被服务委托 SBMainWorkspace 拒绝 原因 安全 权利 启动需要 com apple frontboard debuga

  • 如何传递通用方法的 lambda 表达式参数以检查 MVC EF 4.0 中的重复项

    我的应用程序中有超过 10 个设置屏幕 在每个数据中 我都必须检查重复数据 例如 这是一个示例代码 private void CheckDuplication AIRLINE airline var AIRLINE context AIRL

  • React Native 不会填满 iPad 上的窗口

    我正在运行的任何 React Native 项目 包括 Facebook 的示例 在 iPad 上看起来都很奇怪 它没有填满屏幕 一切看起来 太大 内容左右各有2个黑条 任何帮助都会很棒 谢谢 解决方案 在 xcode 项目中 转到常规选项

  • 使用javascript获取具有多个下拉菜单的选项的选定值

    我有多个功能 其中有多个选项 在选择某个选项时需要更新这些选项 我还需要通过属性元素传递第三条数据 getElementById 适用于单个下拉菜单 但是当页面上有多个菜单时如何使其工作 我努力了var e document getElem

  • jQuery stop(true, true) 跳转到队列中所有动画的末尾

    我一直在使用 jQuerystop true true 方法清除正在运行的动画 以便下一个立即开始 我注意到第一个参数 clearQueue 清除整个动画队列 但第二个参数 jumpToEnd 仅跳转到当前正在运行的动画的末尾 而不是从队列

  • 如何静音AVPlayer中播放的视频？

    我正在 AVPlayer 中播放视频 现在我需要在播放时单独静音音频 请建议如何在 Objective C 中进行操作 谢谢 苏雷什 从iOS7开始你可以设置AVPlayerisMuted财产给true 在 Objective C 中 该属

  • 在 Entity Framework 4.1 Code First 中排除列可更新

    有谁知道我们是否可以在 Entity Framework 4 1 Code First 中排除列的更新 例如 我有 CreatedOn 字段 我不想在进行编辑 更新时包含该字段 这是否可能 即有选择地从 EF Code First 4 1

  • Java Swing：GUI 未更新某些属性

    编辑 下面是一个最简单 最简单且可检查的问题 RESUME 我正在做一个拉丁方应用程序 它设置一个大小为 s 的正方形 并且您需要使用一些限制来为其着色 例如同一行或同一列中的颜色不同 但我的麻烦不是问题本身 而是Swing 我正在尝试使用

  • 求矩阵中不同行和列的元素总和的最大值

    我有一个 nxm 矩阵 我需要找到不同行和列中其值之和的最大值 例如考虑以下矩阵 m1 m2 m3 n1 1 2 3 n2 4 5 6 n3 7 8 9 n4 10 11 12 最大值为 12 8 4 24 请注意 查找最大值并消除属于该列

热门标签