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

 找回密码
 立即注册
  • 李英爱新剧《师任堂》接档《蓝海传说》 26日首播
  • 48岁许晴与友人庆生 素颜出镜似18岁少女
  • 林允牙齿大变样 网友惊呼认不出
  • 姚晨三亚度假摘芒果 偶遇儿时同学趣事多
  • 赵丽颖有新恋情?邓超一不小心提到了她男朋友
  • 林心如谈“幸福”的定义:每天都在笑
  • 外媒称中国正在研发百亿亿次超级计算机
  • 邓超狂晒打篮球帅照 孙俪冷回10字笑翻众人
  • 48亿:北京打造全球最亮“慧眼”
  • 中国基建狂魔:11072米世界第一航道桥合龙
  • 中国建立了146亿美元的互联网投资基金
  • 历届美国总统经历的市场
  • 市场:特朗普就任的第一周
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3021|回复: 21

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

[复制链接]

18

主题

227

帖子

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
回复 百度谷歌雅虎搜狗搜搜有道360奇虎

举报

14

主题

79

帖子

109

积分

注册会员

Rank: 2

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

--

27

主题

105

帖子

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

14

主题

68

帖子

102

积分

注册会员

Rank: 2

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


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

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

22

主题

85

帖子

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?

25

主题

89

帖子

127

积分

注册会员

Rank: 2

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


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

21

主题

92

帖子

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
--

19

主题

87

帖子

127

积分

注册会员

Rank: 2

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


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

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



--

25

主题

87

帖子

139

积分

注册会员

Rank: 2

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



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


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

25

主题

97

帖子

147

积分

注册会员

Rank: 2

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



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


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

本版积分规则

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

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

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

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

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