美国华人网FuninUSA|唐人社区|北美华人论坛:找好货,找礼品卡,找折扣,找工作,找内推,找项目,找股票

 找回密码
 立即注册
  • 这只公猫被封杀宿舍楼外 因为它搞大了10只母猫的肚子
  • 结婚时遇上海军表演 这画面永生难忘
  • 明明有荤有素 汉堡却是真正的“垃圾食品”
  • 英国BA航空IT系统宕机:伦敦起飞航班全挂了!
  • 大开眼界:世界上第一台ATM机原来是这样
  • 史上最诡异恒星:我们第一次看到了外星人?
  • 比特币翻倍狂涨:幕后推手竟是一家投资信托
  • 陈欧3亿投资的街电曝人事震荡:集体离职、手撕东家
  • 柯洁三战AlphaGo皆败 李世石:他应得到掌声
  • 上海迪士尼京东旗舰店开业:可直接买票
  • 当亚马逊股价触及999美元之后,它的下一步是什么?
  • 纳斯达克指数:1996年以来从未出现过……
  • 百思买从零售大灾难中逃脱了?
  • 美国新神——苹果、亚马逊、Netflix、谷歌……
  • 美国恶少屡次欺凌华人老妇其曾经犯下持枪抢劫故意纵火案
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3038|回复: 21

内推面经 -请教一道算法题,各位大牛麻烦指导指导- 唐人社区|北美华人论坛

[复制链接]

19

主题

235

帖子

279

积分

中级会员

Rank: 3Rank: 3

积分
279
QQ
发表于 2016-11-20 15:29:00 | 显示全部楼层 |阅读模式
分享到:
{$content}

唐人社区-北美华人论坛-内推面经版-请教一道算法题,各位大牛麻烦指导指导



JobHunting
标 题: 请教一道算法题,各位大牛麻烦指导指导


一个NxN的matrix,每个cell里面存的是integer, 0到k之间,这个matrix的每行每列的
和都等于k(k是odd),现在要从matrix里面选出一些cell,满足以下条件:
1. 如果一个cell的值是c (0【中国海淘拼单总群】36382164
回复 百度谷歌雅虎搜狗搜搜有道360奇虎

举报

16

主题

83

帖子

117

积分

注册会员

Rank: 2

积分
117
QQ
发表于 2016-11-20 17:11:26 | 显示全部楼层
JobHunting
标  题: Re: 请教一道算法题,各位大牛麻烦指导指导


这是一个operations research的问题吧,用integer programming 解:

Maximize/minimize: sum(Xij)

Subject to:
sum(Xij, i=1..n) == 2, for each j in 1..m
sum(Xij, j=1..m) == 2, for each i in 1..n
Xij <= Cij for all i, j

Objective function不重要,找到feasible solution就行了

--

29

主题

111

帖子

171

积分

注册会员

Rank: 2

积分
171
QQ
发表于 2016-11-20 17:14:12 | 显示全部楼层
JobHunting
标  题: Re: 请教一道算法题,各位大牛麻烦指导指导



【 在 invalid (浮夸) 的大作中提到: 】
: 一个NxN的matrix,每个cell里面存的是integer, 0到k之间,这个matrix的每行每列的
: 和都等于k(k是odd),现在要从matrix里面选出一些cell,满足以下条件:
: 1. 如果一个cell的值是c (0<c<=k),那么这个cell可以选重复选c次。若是c=0则表
: 示该cell不可选;若c=1则表示该cell只能被选一次。
: 1. 每行必须选中两次(两个不同的cell各选一次,或者同一个cell选两次)。
: 2. 每列必须选中两次(两个不同的cell各选一次,或者同一个cell选两次)。
: 图中的例子圈着的是两个例子(k=3)的solution,一个圈代表选了一次,两个圈代表
: 选了两次。这个最优的解法是什么?



--



此主题相关图片如下:1.png
(70503 字节) [删除]

14

主题

75

帖子

109

积分

注册会员

Rank: 2

积分
109
QQ
发表于 2016-11-20 17:23:19 | 显示全部楼层
JobHunting
标  题: Re: Re:请教一道算法题,各位大牛麻烦指导指导


優化在於如何剪枝,把不合適的剪掉或只遍歷可能的combination。不過坐等看有沒有
其他更優解法。

【在invalid(浮夸)的大作中提到:】
:不断遍历的话这个时间复杂度是不是就挺高的了?
--

23

主题

92

帖子

141

积分

注册会员

Rank: 2

积分
141
QQ
发表于 2016-11-20 17:28:16 | 显示全部楼层
JobHunting
标  题: Re: 请教一道算法题,各位大牛麻烦指导指导


是要找出所有的选法吗?

【 在 invalid (浮夸) 的大作中提到: 】
: 一个NxN的matrix,每个cell里面存的是integer, 0到k之间,这个matrix的每行每列的
: 和都等于k(k是odd),现在要从matrix里面选出一些cell,满足以下条件:
: 1. 如果一个cell的值是c (0<c<=k),那么这个cell可以选重复选c次。若是c=0则表
: 示该cell不可选;若c=1则表示该cell只能被选一次。
: 1. 每行必须选中两次(两个不同的cell各选一次,或者同一个cell选两次)。
: 2. 每列必须选中两次(两个不同的cell各选一次,或者同一个cell选两次)。
: 图中的例子圈着的是两个例子(k=3)的solution,一个圈代表选了一次,两个圈代表
: 选了两次。这个最优的解法是什么?



--
Look. If you had one shot or one opportunity to seize everything you ever wanted in one moment.
Would you capture it or just let it slip?

27

主题

98

帖子

155

积分

注册会员

Rank: 2

积分
155
QQ
发表于 2016-11-20 17:30:31 | 显示全部楼层
JobHunting
标  题: Re:请教一道算法题,各位大牛麻烦指导指导


正路看著像back tracking的題,只有不斷遍歷找解,類似於soduku的變種。
--

23

主题

98

帖子

153

积分

注册会员

Rank: 2

积分
153
QQ
发表于 2016-11-20 17:53:52 | 显示全部楼层
JobHunting
标  题: Re: 请教一道算法题,各位大牛麻烦指导指导


网络流吧,建立源点S,汇点T
每个行一个点Xi,每个列一个点Yj
S->Xi capacity=2
Yj->T capacity=2
Xi->Yj capacity=min(2,cell_ij's value)

Has solution if and only if max flow (2N) is reached
--

22

主题

95

帖子

146

积分

注册会员

Rank: 2

积分
146
QQ
发表于 2016-11-20 17:57:32 | 显示全部楼层
JobHunting
标  题: Re: Re:请教一道算法题,各位大牛麻烦指导指导


backtrack的复杂度向来都高
指数级不是梦

【 在 invalid (浮夸) 的大作中提到: 】
: 不断遍历的话这个时间复杂度是不是就挺高的了?



--

25

主题

94

帖子

148

积分

注册会员

Rank: 2

积分
148
QQ
发表于 2016-11-20 18:11:32 | 显示全部楼层
JobHunting
标  题: Re: Re:请教一道算法题,各位大牛麻烦指导指导



【 在 zou2016 (middleboy) 的大作中提到: 】
: 正路看著像back tracking的題,只有不斷遍歷找解,類似於soduku的變種。


不断遍历的话这个时间复杂度是不是就挺高的了?
--

30

主题

110

帖子

168

积分

注册会员

Rank: 2

积分
168
QQ
发表于 2016-11-20 18:12:52 | 显示全部楼层
JobHunting
标  题: Re: 请教一道算法题,各位大牛麻烦指导指导



【 在 coldknight (冷骑士) 的大作中提到: 】
: 是要找出所有的选法吗?


只需要找出一个就好了
--
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

美国华人网|唐人社区|什么值得买FunInUSA.net发布的内推面经 -请教一道算法题,各位大牛麻烦指导指导- 唐人社区|北美华人论坛帖子由网友提供或转载于网络,若发布的内推面经 -请教一道算法题,各位大牛麻烦指导指导- 唐人社区|北美华人论坛侵犯了您的权益,请联系我们.
Sasa.com

Copyright ©2011 FunInUSA.NET All Right Reserved.  Powered by Discuz! X3.0 小黑屋

本站信息均由会员发表,不代表美国华人网FunInUSA|唐人社区的立场,如侵犯了您的权利请发帖投诉  技术支持: 美国华人网FunInUSA|唐人社区

安全联盟认证 安全联盟认证

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