免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
12下一页
最近访问板块 发新帖
查看: 3483 | 回复: 10

[算法] 关于背包问题的一点考虑。 [复制链接]

论坛徽章:
2
2015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:56:11
发表于 2014-08-30 21:54 来自手机 |显示全部楼层
如果小偷面对一大堆财宝,对于每件只有一次机会选择拿还是不拿。这种情况下如何偷盗更值钱的财宝。这应该是个实际的问题。

论坛徽章:
2
2015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:56:11
发表于 2014-08-30 21:58 来自手机 |显示全部楼层
也就是说需要多次比较财宝价值和体积的算法统统无效。

论坛徽章:
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
发表于 2014-08-30 22:02 |显示全部楼层
cobras 发表于 2014-08-30 21:54
如果小偷面对一大堆财宝,对于每件只有一次机会选择拿还是不拿。这种情况下如何偷盗更值钱的财宝。这应该是 ...


如果你的意思是:

1、小偷只能拿一件。
2、而且只能有一次选择的机会,放弃了就不能拿了,即使发现后面的财宝都没有这个值钱。

论坛徽章:
2
2015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:56:11
发表于 2014-08-30 22:10 来自手机 |显示全部楼层
我的意思大概就是2。是我表述不清。嗨,语文没学好。

论坛徽章:
2
2015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:56:11
发表于 2014-08-30 22:14 来自手机 |显示全部楼层
我为啥这样想,因为偷东西的时候大概时间都比较紧,可供比较选择的时间可不多。

论坛徽章:
35
双子座
日期:2014-05-09 17:56:38程序设计版块每日发帖之星
日期:2015-08-30 06:20:00程序设计版块每日发帖之星
日期:2015-12-24 06:20:0015-16赛季CBA联赛之上海
日期:2015-12-27 11:07:07程序设计版块每日发帖之星
日期:2016-01-12 06:20:0015-16赛季CBA联赛之北京
日期:2016-01-15 01:01:2115-16赛季CBA联赛之浙江
日期:2016-01-15 22:38:20程序设计版块每日发帖之星
日期:2016-01-18 06:20:00每日论坛发贴之星
日期:2016-01-18 06:20:0015-16赛季CBA联赛之北控
日期:2016-01-30 21:43:01程序设计版块每日发帖之星
日期:2016-02-08 06:20:0015-16赛季CBA联赛之山西
日期:2016-02-20 10:54:41
发表于 2014-08-30 22:17 来自手机 |显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽

论坛徽章:
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
发表于 2014-08-30 22:18 |显示全部楼层
这个不是算法问题了,这个是数学问题了,以前上学的接触过。

http://zh.wikipedia.org/wiki/%E7%A7%98%E6%9B%B8%E5%95%8F%E9%A1%8C

http://en.wikipedia.org/wiki/Secretary_problem

   

论坛徽章:
2
2015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:56:11
发表于 2014-08-30 22:39 来自手机 |显示全部楼层
第一个被墙了。第二个秘书问题没看到策略是什么?可能英文不太好。

论坛徽章:
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
发表于 2014-08-31 11:21 |显示全部楼层
貌似最优策略是过掉前面的1/3,之后遇到比前面好的就接受。

可以搞个蒙特卡洛来模拟一下,看看对不对。

论坛徽章:
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
发表于 2014-08-31 11:22 |显示全部楼层
首先还需要预判一下大概有多少人来面试(有多少个宝物),然后才知道多少是1/3。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP