免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
楼主: snowboy9859

[算法] 搜狐2012牛逼笔试题,至今无思路,求牛人指点 [复制链接]

论坛徽章:
0
发表于 2011-10-10 15:17 |显示全部楼层
经典 0-1 背包算法啊!用动态规划做

论坛徽章:
0
发表于 2011-10-10 18:47 |显示全部楼层
背包问题

这里可以理解质量和权值都是实数值
状态转移方程
f(n)(v) = min{|f(n-1)(v)-M|,|f(n-1)(v-xn)-M|};
编程注意这里是实数,即存在小数。
时间复杂度O(N*M*k),k取决于min你怎么实现的。

论坛徽章:
0
发表于 2011-10-13 17:53 |显示全部楼层
把所有可能的结果全部计算出来,直接查。

o(1)

哈哈哈

论坛徽章:
0
发表于 2011-10-13 17:54 |显示全部楼层
不过,把所有可能的结果计算出来的复杂度是0(n^2)

论坛徽章:
0
发表于 2011-10-14 16:55 |显示全部楼层
01背包,把M当作ceil(M)来处理。

论坛徽章:
89
水瓶座
日期:2014-04-01 08:53:31天蝎座
日期:2014-04-01 08:53:53天秤座
日期:2014-04-01 08:54:02射手座
日期:2014-04-01 08:54:15子鼠
日期:2014-04-01 08:55:35辰龙
日期:2014-04-01 08:56:36未羊
日期:2014-04-01 08:56:27戌狗
日期:2014-04-01 08:56:13亥猪
日期:2014-04-01 08:56:02亥猪
日期:2014-04-08 08:38:58程序设计版块每日发帖之星
日期:2016-01-05 06:20:00程序设计版块每日发帖之星
日期:2016-01-07 06:20:00
发表于 2011-10-15 00:33 |显示全部楼层
这个问题可以使用遗传算法来求解,不保证全局最优,但是应该能算一个不错的解。

论坛徽章:
0
发表于 2011-10-16 18:16 |显示全部楼层
我说一下我的想法:
1、用0-1背包求出比M小的最大的选取方法。
2、设给定的N个数的和为SUM,那么再用一次0-1背包算法求出(SUM-M)的取法,那么没取的数就是大于M的情况下最接近M的取法。
综合1、2就可以找到最接近的取法。

时间复杂度也就是0-1背包的啦。

这个时间复杂度可以满足要求吗?

论坛徽章:
0
发表于 2011-10-16 18:17 |显示全部楼层
看错了,是实数啊。。。

论坛徽章:
0
发表于 2011-10-17 10:57 |显示全部楼层
二分法

论坛徽章:
0
发表于 2011-11-13 22:44 |显示全部楼层
回复 18# koolcoy
您在第二步中说的dp是什么意思{:3_196:} ,您能说的再详细一些吗?
您讲的这三大步所得到的结果,我觉得是对的,因为考虑了所有的情况。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP