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

 找回密码
 立即注册

点击进入授权页面

只需一步,快速开始

  • 熊黛林晒自拍秀性感 被指故意拉低衣服
  • 葛优诉某网站擅用“葛优躺” 索赔40万元
  • 林丹“出轨门”后首发声 感谢粉丝:我会努力
  • 李东旭金高银领衔《鬼怪》开播 情节爆表演技高
  • 唐嫣罗晋公布恋情后,胡歌彭于晏成“国民单身狗”?
  • 环球风尚盛典圆满落幕 杨澜、陆川等被授予风尚领秀
  • 张伦硕赞钟丽缇皮肤超好身材超棒 自曝要一年内造人
  • 姚明女儿才6岁 身高就超过了妈妈的腰
  • 澳洲男子跳进河里救考拉 那画面太喜感
  • 口水直流!在大学寝室做饭还能这么玩
  • 明年第一季度美国地产可能成为交易高峰期-美国房产信息
  • 美元资产是海外置业的优秀配置,未来升值空间可观-美国房产信息
  • 经济学家:希腊可能从欧洲的政治动荡获利
  • 克莱姆对新股票市场的态度:升息或死亡
  • 市场反弹继续,但注意漏洞
  • 策略师斯托瓦尔:11月的强势不会偷走12月的收益
  • 摩根大通首席执行官说可能发布特别股息
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3007|回复: 20

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

[复制链接]
TA在交友中心
0 0 38
  @ME:   

18

主题

225

帖子

268

积分

中级会员

Rank: 3Rank: 3

积分
268
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
微信公众号】funinusa : 每日微信滚动更新美国市场打折团购折扣Coupon讯息。
回复 百度谷歌雅虎搜狗搜搜有道360奇虎

举报

TA在交友中心
0 0 29
  @ME:   

13

主题

76

帖子

102

积分

注册会员

Rank: 2

积分
102
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就行了

--

TA在交友中心
0 0 55
  @ME:   

27

主题

102

帖子

148

积分

注册会员

Rank: 2

积分
148
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 字节) [删除]
TA在交友中心
0 0 32
  @ME:   

13

主题

67

帖子

92

积分

注册会员

Rank: 2

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


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

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

20

主题

82

帖子

124

积分

注册会员

Rank: 2

积分
124
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?
TA在交友中心
0 0 54
  @ME:   

25

主题

86

帖子

127

积分

注册会员

Rank: 2

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


正路看著像back tracking的題,只有不斷遍歷找解,類似於soduku的變種。
--
TA在交友中心
0 0 48
  @ME:   

21

主题

89

帖子

130

积分

注册会员

Rank: 2

积分
130
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
--
TA在交友中心
0 0 46
  @ME:   

19

主题

87

帖子

127

积分

注册会员

Rank: 2

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


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

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



--
TA在交友中心
0 0 55
  @ME:   

25

主题

87

帖子

139

积分

注册会员

Rank: 2

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



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


不断遍历的话这个时间复杂度是不是就挺高的了?
--
TA在交友中心
0 0 49
  @ME:   

24

主题

94

帖子

133

积分

注册会员

Rank: 2

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



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


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

本版积分规则

玩美生活FunInUSA.net 华人娱乐论坛发布的内推面经 -请教一道算法题,各位大牛麻烦指导指导- 唐人社区|北美华人论坛帖子由网友提供或转载于网络,若发布的内推面经 -请教一道算法题,各位大牛麻烦指导指导- 唐人社区|北美华人论坛侵犯了您的权益,请联系我们.
1&1 Hosting

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

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

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

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