| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 5332 人关注过本帖
标题:【此帖作废】[非c高手进]帮忙编程解决这两道小学奥数题
只看楼主 加入收藏
liyanhong
Rank: 3Rank: 3
来 自:水星
等 级:禁止访问
威 望:8
帖 子:1867
专家分:0
注 册:2008-5-3
收藏
得分:0 
[bo][un]卧龙孔明[/un] 在 2008-8-6 09:07 的发言:[/bo]



我不希望留给他人一个错误说法。
我最后详细地说一下DP和bit组合两种算法的复杂度差异
对于01背包,设N为最大的体积(这里就是可能组成的最大钱数),则复杂度为O(N^2)
对于用bit组合的方法,设M为物品的种类 ...

说的像哈夫曼树一样
帖个代码不好吗?

爱上你 是 我的错  可是离 开  又舍不得  听着你为我写的歌     好难过
如果说 我说如果  我们还 能  重新来过   不去计 较 谁对谁错  会怎么做
2008-09-04 12:16
liyanhong
Rank: 3Rank: 3
来 自:水星
等 级:禁止访问
威 望:8
帖 子:1867
专家分:0
注 册:2008-5-3
收藏
得分:0 
[bo][un]卧龙孔明[/un] 在 2008-8-5 23:33 的发言:[/bo]


...算了,我有时间写个代码吧....

而且刚才算了一下,复杂度不是O(N)...当时想错了,复杂度是2^N....看起来还没有背包问题速度快...
我收回之前说的话,这个题,此方法并非最佳解法,最佳解法还是0-1背包的DP方 ...

期待

爱上你 是 我的错  可是离 开  又舍不得  听着你为我写的歌     好难过
如果说 我说如果  我们还 能  重新来过   不去计 较 谁对谁错  会怎么做
2008-09-04 12:18
快速回复:【此帖作废】[非c高手进]帮忙编程解决这两道小学奥数题
数据加载中...
 
   



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

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