找回密码
 欢迎注册
查看: 11357|回复: 2

[讨论] 有没有尽可能简单的解决方法

[复制链接]
发表于 2015-11-15 22:28:49 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
A是一个m×n阶矩阵,其元素为非负整数。
在每一行的最右边(矩阵外)写出了该行中最大的数。
在每一列的最下边(矩阵外)写出了该列中最大的数。
求矩阵所有元素之和的最小值.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2015-11-15 22:31:58 | 显示全部楼层
记各行的最大值为`\{a_1,a_2,\cdots,a_m\}`, 各列的最大值为`\{b_1,b_2,\cdots,b_n\}`.
由于排列顺序并不重要,不妨假定这两个最值表是按升序排列的。(显然,`a_m=b_n`,为A中的最大元)
最极端的情况就是`m=n`, 且`\{a_1,a_2,\cdots,a_m\}=\{b_1,b_2,\cdots,b_n\}`,那么最小和就是`\sum a_i`或`\sum b_i`.
比如下面这个样子
                        1
                        2
                        3
1        2        3       

最小和就是6,相应的最小矩阵为:
1        0        0       
0        2        0       
0        0        3

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2015-11-19 00:18:13 | 显示全部楼层
假定`\{c_1,c_2,\cdots,c_t\}=\text{Union}\{a_1,a_2,\cdots,a_m,b_1,b_2,\cdots,b_n\}`(Union函数删除重复元素,只留1个)
那么最小和等于 `d_1c_1+d_2c_2+\cdots+d_ic_i+\cdots+d_tc_t`,
这里`d_i`是`c_i`在`\{a_1,a_2,\cdots,a_m\} `或`\{b_1,b_2,\cdots,b_n\}`中的重数,取较大者。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 00:00 , Processed in 0.042642 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表