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

 找回密码
 立即注册
  • 刘烨过39岁生日感慨:不敢再装三十几岁的男孩子
  • 操心太多?被传赴美陪产的陈冠希怎么这么显老
  • 徐静蕾公开与男友相处细节:他做事比我果断
  • 影版《奶酪陷阱》又有新人加入 朴山多拉演女主好友
  • 亮点太多!赵薇怀抱"小沈阳" 身后的苏有朋亮了
  • 杨坤恋情曝光!揭秘他至今不婚不育的隐情
  • 小沈阳搂张柏芝合唱 手放在这个部位有点尴尬
  • 余文乐自认说错话:不是被逼承认恋情 想保护对方
  • 罗晋绯闻女友苗圃复出 嫁大21岁富商变豪门阔太
  • 回归家庭做奶爸 陈思诚逛婴幼儿店认真挑玩具
    Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
    ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
    搜索
    查看: 3030|回复: 21

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

    [复制链接]

    18

    主题

    233

    帖子

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

    举报

    15

    主题

    81

    帖子

    114

    积分

    注册会员

    Rank: 2

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

    主题

    109

    帖子

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

    14

    主题

    68

    帖子

    102

    积分

    注册会员

    Rank: 2

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


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

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

    22

    主题

    89

    帖子

    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

    主题

    91

    帖子

    146

    积分

    注册会员

    Rank: 2

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


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

    22

    主题

    94

    帖子

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

    20

    主题

    91

    帖子

    138

    积分

    注册会员

    Rank: 2

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


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

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



    --

    25

    主题

    91

    帖子

    139

    积分

    注册会员

    Rank: 2

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



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


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

    27

    主题

    100

    帖子

    155

    积分

    注册会员

    Rank: 2

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

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

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