美国华人网FuninUSA_唐人社区_北美华人论坛:找礼品卡,找折扣,找报价,找工作,找内推,找项目,找股票

 找回密码
 立即注册
  • AMC宣布续订《深入恶土》第三季
  • 每喝一罐无糖饮料 就离老年痴呆更近一步
  • 美国一男子喝醉酒狂殴硅谷明星机器人:惨遭逮捕
  • 高压水刀威力到底有多大?暴力切割电磁炉
  • 丹麦生蚝泛滥成灾官微求助 吃货不淡定了
  • 癌症 为啥一发现就是晚期?无奈……
  • 科学家称地球存外星文明技术证据:藏于地下
  • 苍蝇爬过的食物千万别吃:原因自己看……
  • 科学家:外星人已出现在地球 景象是这样
  • 世界最大兔子搭美联航飞机转移:竟途中暴毙
  • 特朗普的狂想——不切实际的公司税计划
  • AMD:增长和损失同在,有改变才会有进步
  • 好消息!纳斯达克指数首破6000点,道指和纳指涨势喜人
  • Tom Lee警示下行风险,揭示市场三大“地雷”
  • 在Buffalo Wild Wings季度财报中出现了“天文误差”
  • 巴菲特该高兴了,IBM加息至每股1.5美元
  • 好消息!纳斯达克指数首破6000点,道指和纳指涨势喜人
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3035|回复: 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
回复 百度谷歌雅虎搜狗搜搜有道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就行了

--

28

主题

111

帖子

166

积分

注册会员

Rank: 2

积分
166
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 字节) [删除]

15

主题

73

帖子

107

积分

注册会员

Rank: 2

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


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

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

22

主题

90

帖子

132

积分

注册会员

Rank: 2

积分
132
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

主题

93

帖子

151

积分

注册会员

Rank: 2

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


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

22

主题

96

帖子

147

积分

注册会员

Rank: 2

积分
147
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
--

21

主题

93

帖子

142

积分

注册会员

Rank: 2

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


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

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



--

25

主题

92

帖子

139

积分

注册会员

Rank: 2

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



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


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

30

主题

108

帖子

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|唐人社区

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

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