| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 7679 人关注过本帖, 1 人收藏
标题:贪心算法求解这道题
只看楼主 加入收藏
BlueGuy
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:29
帖 子:4476
专家分:4055
注 册:2009-4-18
收藏
得分:0 
以下是引用边小白在2015-6-11 06:51:30的发言:

哈哈哈!做不来就承认做不来嘛,还不死心整些什么数据结构、二叉树、DFS等这些糊弄人的名词,我也会说这些词,但我知道我不懂这些,要学习这些,同时我也知道:我将来即使懂这些,会灵活运用这些,我也不可能自诩为神,我深知“强中自有强中手,一山更比一山高”。
对了,我知道二分法的。初中时老师让用纸和笔开平方,我总比别人做的快。后来百度了,才知道我用的是二分法,那时我们要精确到小数点后3位,大神,你能把它变成代码吗?精确到小数点后6位就行了。

我的代码是能算出结果的,只是速度慢了点,

我就是真命天子,顺我者生,逆我者死!
2015-06-11 07:45
BlueGuy
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:29
帖 子:4476
专家分:4055
注 册:2009-4-18
收藏
得分:0 
我做题目不是套公式,是找他为什么慢,为什么能优化
不是只看速度的,也看结果的。

我不是什么题都做的,对我没有价值的题目我是不会浪费时间解的,
恰好这个题目我有点兴趣,准备花点时间仔细研究研究
做游戏不是看谁解的题多哦,

[ 本帖最后由 BlueGuy 于 2015-6-11 08:31 编辑 ]

我就是真命天子,顺我者生,逆我者死!
2015-06-11 07:56
pycansi
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:5
帖 子:418
专家分:1060
注 册:2012-7-26
收藏
得分:0 
才发现这边这么热闹


莫问前尘有愧,但求今生无悔
2015-06-11 09:36
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:216
帖 子:2039
专家分:11273
注 册:2014-12-6
收藏
得分:0 
回复 56楼 BlueGuy
你可以试试我的方法,看能不能提高速度。
首先,你要知道这里用的是组合,不是全排列,因此做a+b后不用再做b+a,全排列那个慢啊,无法容忍;其次,即使是组合,针对该题意,你也不需要对集合里的所有元素进行组合,而是只需要和符合条件的元素组合,比如容量20,已经有一个元素15在袋子里,那你下次放进袋子里的元素必定小于或等于20-15,这样就略过了6-20之间的数不需要组合了,这样可极大减少递归次数,提高速度(我不知道这是不是所谓的动态规划);第三,只要组合出和容量相等的组合后可立即退出递归,这已经是最优的了;第四,当经过一轮递归后,你已经输出了所有的等于袋子容量的最优解,余下的组合可能不能等于袋子容量,比如,可能有一大批=19的解是最优的,这时你可以调整袋子容量为19,也可以提高获取最优组合的速度;第五,函数递归结束都不能得到最优解的,就需要放弃上一轮递归时加入的数据,跳到下一个数据组合,看能否得到最优解,这大概就是所谓剪枝,这个剪枝的过程可能一直发生到最原始的递归,即放弃一整个组合,跳至下一个组合重新开始;第六,当然就是用合理的算法把最优组合的子集从原始集合中分离出来,要注意,原始集合中有相同数据,只要碰到第一个相同的就退出比较,不要把原始集合的所有相同的元素都earse掉了;第七,就是要理解函数递归了,不然很容易自己转进去转不出来的,用函数递归得到符合条件的组合结果相当于做n+1的循环嵌套和n进行组合得到的结果,比如5组3,则第一层循环是1-3,第二层是2-4,第三层是3-5,循环完了组合也就完成了;最后,以上分析纯个人想法,有不当之处望指正,希望对你有帮助。

能编个毛线衣吗?
2015-06-11 10:15
纳兰伽香
Rank: 10Rank: 10Rank: 10
来 自:北京
等 级:贵宾
威 望:10
帖 子:426
专家分:1650
注 册:2015-4-5
收藏
得分:0 
好久没来  忽然这么热闹  而且的我的版主没啦  这个问题  用动态规划法  最优解进行解决吧  估计没学过  数学模型的孩子  解起来很费劲  至于什么2分法之类的  我感觉没必要啊  周末我来做做 争取拿到y版的1000分

风回小院庭芜绿,柳眼春相续
2015-06-11 10:33
BlueGuy
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:29
帖 子:4476
专家分:4055
注 册:2009-4-18
收藏
得分:0 
回复 59楼 wmf2014
嗯,我求的是所有可能的组合,
你说的好像没什么作用

// 比如容量20,已经有一个元素15在袋子里,那你下次放进袋子里的元素必定小于或等于20-15,这样就略过了6-20之间的数不需要组合了

怎么略过?

[ 本帖最后由 BlueGuy 于 2015-6-11 12:05 编辑 ]

我就是真命天子,顺我者生,逆我者死!
2015-06-11 11:58
lianyicq
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:26
帖 子:737
专家分:3488
注 册:2013-1-26
收藏
得分:0 
大家都是磨刀霍霍,勇力,闯劲令人敬佩。
如果真正有兴趣,可以参看http://en.
如果还愿意尝试,敢于挑战,可以参考http://www.
不过就算编程知识很丰富,经验很老到,掌握所有编程语法,没有编程外的知识.给出了关键代码,仍然是谜中谜.
如果做到了,效果比现有的方法效率更高,完全有必要发论文到SCI,是不是可以令业界的专家学者汗颜。
有条件也可以在知网上查查有关文献。

大开眼界
2015-06-11 12:53
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:216
帖 子:2039
专家分:11273
注 册:2014-12-6
收藏
得分:0 
回复 61楼 BlueGuy
这...,你怎么的也是写了好几年游戏的,这个怎么实现应该不需要手把手教吧。我在32楼代码注释部分写的很详细,今天我对该代码做了优化,去掉了不必要的语句,自认为已完成一楼需求,自己未测试到bug。有兴趣可以参考下。

能编个毛线衣吗?
2015-06-11 19:14
lianyicq
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:26
帖 子:737
专家分:3488
注 册:2013-1-26
收藏
得分:0 
回复 32楼 wmf2014
历害!没用任何优化方法.
楼主的问题被轻描淡写的实现,可以考虑二维和三维问题.这种水平代码也没必要贴上来。
可以了解了解目前这类问题的研究进展,以及如何评估算法,试着投稿吧。

大开眼界
2015-06-12 11:13
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:216
帖 子:2039
专家分:11273
注 册:2014-12-6
收藏
得分:0 
回复 64楼 lianyicq
还是在剪枝上出了问题。
  开始没有return 3的返回,测试1楼和8楼数据没问题的,后发现做1000以上数据时有死循环的可能(不是每次),经单步发现是递归到最后数据集的数据永远没有c子集的数据优,所以不断地剪枝加数据、再剪枝加数据,就出不来了,如是加了句剪整枝的返回(if(!s[p]return 3;),发现没死循环,加上目测好像没多大问题,所以就直接发了,没有再测试小数据。目前再次修改为“if(!s[p]&&sumarry(t)!=sumarry(c))return 3; ”,可以正确通过1楼和8楼的数据测试(3 4 6 3 7 9 45 2 10、5 4 3 2 2 2 2),测试1000个以上数据无延时,目测正常(主要检测不等于包容量的数据)。
  另:lianyicq版主,感谢你指正,发现问题,直接指出为好,无需冷嘲热讽,大家都是因为技术兴趣走到一个板块,没有厉害冲突。
图片附件: 游客没有浏览图片的权限,请 登录注册

图片附件: 游客没有浏览图片的权限,请 登录注册


[ 本帖最后由 wmf2014 于 2015-6-12 15:06 编辑 ]

能编个毛线衣吗?
2015-06-12 14:49
快速回复:贪心算法求解这道题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.028343 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved