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

 找回密码
 立即注册
  • NASA神秘发现:超越太阳系!
  • 欧洲惊现致命放射性粒子 科学家都蒙了
  • 澳洲一轻型飞机撞上商场坠毁 5人全部死亡
  • 科学家破译蝙蝠聊天内容:对飙垃圾话
  • 范冰冰穿花衣旧照曝光 网友调侃:还以为是谢大脚
  • 杨幂揪心想念女儿 硬起来保护家庭:别说我家人
  • 高晓松晒收藏的《金瓶梅》 书都被读烂了
  • 宇宙神秘难解之题:中国科学家搞定了
  • 历史首次!杨振宁弃美国国籍 转为中科院院士
  • 淘宝违反“广告法”?被起诉索赔20万
  • 星巴克:零售渠道发展
  • 大多退休职工仍在继续工作
  • AMD“Ryzen”:试图占据更多市场份额
  • 机器人会导致失业,我们需要提前做准备
  • Square股票超出预期,上涨44%
  • 美国各地雇员加入“无移民”抗议活动而被解雇
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3027|回复: 21

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

[复制链接]

18

主题

229

帖子

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 : 每日滚动更新美国市场折扣资讯微商进货首选资讯渠道。
回复 百度谷歌雅虎搜狗搜搜有道360奇虎

举报

14

主题

80

帖子

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

主题

108

帖子

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

主题

87

帖子

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?

26

主题

90

帖子

146

积分

注册会员

Rank: 2

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


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

21

主题

92

帖子

144

积分

注册会员

Rank: 2

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

20

主题

90

帖子

138

积分

注册会员

Rank: 2

积分
138
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的變種。


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

26

主题

99

帖子

152

积分

注册会员

Rank: 2

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

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

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