【此帖作废】[非c高手进]帮忙编程解决这两道小学奥数题 - C语言论坛

编程论坛 → 开发语言 → 『 C语言论坛』 → 【此帖作废】[非c高手进]帮忙编程解决这两道小学奥数题

标题：【此帖作废】[非c高手进]帮忙编程解决这两道小学奥数题

只看楼主

liyanhong

来　自：水星
等　级：禁止访问
威　望：8
帖　子：1867
专家分：0
注　册：2008-5-3

第 61 楼

得分: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

来　自：水星
等　级：禁止访问
威　望：8
帖　子：1867
专家分：0
注　册：2008-5-3

第 62 楼

得分:0

[bo][un]卧龙孔明[/un] 在 2008-8-5 23:33 的发言：[/bo]

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

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

期待

爱上你是我的错可是离开又舍不得听着你为我写的歌好难过
如果说我说如果我们还能重新来过不去计较谁对谁错会怎么做

2008-09-04 12:18

参与讨论请移步原网站贴子：https://bbs.bccn.net/thread-226205-1-1.html