免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 2372 | 回复: 3

[算法] 询问各算法 [复制链接]

论坛徽章:
0
发表于 2011-06-27 10:52 |显示全部楼层
有2n个数,从中选出N个数使其和最接近  2N个数总和的一半

例如
1,2,2,4,6,7  这6个数从中选出3个数使其和等于 (1+2+2+4+6+7)/2


如何和是奇数
1,2,3,4,6,7  就从中选择出3个数使其最接近(1+2+3+6+7)/2  


求这个优化算法!

或者说讨论指点一下也可以!

论坛徽章:
2
白羊座
日期:2013-11-18 19:52:42辰龙
日期:2014-09-07 07:46:06
发表于 2011-06-27 11:02 |显示全部楼层
先排序A0..An,并求出sum(A0..An)/4,以sum(A0..An)/4为中点,依次取一大于sum(A0..An)/4的某数比如Ak,然后用贪心算法,取出小于sum(A0..An)/4端的两个数值。并令三数的和与sum(A0..An)/4之差的绝对值最小。

论坛徽章:
0
发表于 2011-07-04 22:21 |显示全部楼层
同问,不知道怎么做

论坛徽章:
3
2015年迎新春徽章
日期:2015-03-04 09:56:11数据库技术版块每日发帖之星
日期:2016-08-03 06:20:00数据库技术版块每日发帖之星
日期:2016-08-04 06:20:00
发表于 2011-07-05 09:22 |显示全部楼层
典型的指数级别算法,无法优化.
或者,你就用贪心来近似吧
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP