[求助]石子归并问题 - C语言论坛

编程论坛 → 开发语言 → 『 C语言论坛』 → [求助]石子归并问题

标题：[求助]石子归并问题

只看楼主

X_ray

等　级：新手上路
帖　子：2
专家分：0
注　册：2007-7-29

第 11 楼

得分:0

以下是引用simpley在2005-9-1 11:22:00的发言：
我认为这是0/1背包问题的变形.不知道大家认为呢?
我在一本书上看到这样的问题还没找到时间复杂度的算法.够难的

明显就是0/1背包, 只不过使用set枚举的那种0/1背包......

2007-07-29 18:50

leeco

等　级：贵宾
威　望：10
帖　子：1026
专家分：177
注　册：2007-5-10

第 12 楼

得分:0

W＜＝100000，是只Wi＜＝100000,i=1,2,...N吗？
如果是的话，DP会超内存，回溯比较慢，N<=20,2^20还不算大，如果剪枝剪的好还是不错的

2007-07-30 14:40

卧龙孔明

等　级：贵宾
威　望：59
帖　子：3872
专家分：684
注　册：2006-10-13

第 13 楼

得分:0

优化后的动态规划
空间复杂度可以降到N,时间复杂度为N*N,可以通过

[此贴子已经被作者于2007-7-31 13:01:23编辑过]

My Blog: www.aiexp.info
虽然我的路是从这里开始的,但是这里不再是乐土.感谢曾经影响过，引导过，帮助过我的董凯,飞燕,leeco,starwing,Rockcarry,soft_wind等等等等.别了,BCCN.

2007-07-31 12:58

cwande

等　级：新手上路
威　望：3
帖　子：333
专家分：0
注　册：2006-8-18

第 14 楼

得分:0

dfs or dp

汗,都懒得写代码了.......... cheat了一个威望，哈．．．．．

2007-08-01 22:09

cwande

等　级：新手上路
威　望：3
帖　子：333
专家分：0
注　册：2006-8-18

第 15 楼

得分:0

以下是引用卧龙孔明在2007-7-31 12:58:00的发言：
优化后的动态规划
空间复杂度可以降到N,时间复杂度为N*N,可以通过

空间复杂度是W,时间复杂度是N*W吧

汗,都懒得写代码了.......... cheat了一个威望，哈．．．．．

2007-08-01 22:20

cwande

等　级：新手上路
威　望：3
帖　子：333
专家分：0
注　册：2006-8-18

第 16 楼

得分:0

以下是引用fzjz08在2005-8-31 10:32:00的发言：
先排序,然后用最大的数减去第二大的数,再减去第三大的数,如过结果大于0,就再减去第四大的树,如果结果小于0,就加上第四大的数,如此循环到最后一个数
比如楼主给的例子
5
5
8
13
27
14
排序后是
27
14
13
8
5
5
运行过程是27-14=13>=0,所以13-13=0>=0,所以0-8=-8<=0,所以-8+5=-3<=0,所以-3+5=2
最终的最小差距应该是2
两堆的分配应该是
27,5,5
14,13,8

我做过一些实验,当差距可以为0的时候,这种算法是可以得出正确结果的.因为没有通过数学证明,如果有什么问题,请多指正

这种贪心的算法明显是错的..............
举个例子
5
10 8 6 4 4
按你的算法得出的答案是4
实际最优的结果是0

汗,都懒得写代码了.......... cheat了一个威望，哈．．．．．

2007-08-01 22:25

totohack

等　级：新手上路
帖　子：133
专家分：0
注　册：2007-7-15

第 17 楼

得分:0

先把“所有堆石头的质量”加起来，得到一个总质量，然后再除2，得出一个数A，

再对“所有堆石头的质量”进行组合，得出的总质量数最接近A，那么这个数与A的差值再乘以2就是结果

难点是“对“所有堆石头的质量”进行组合”

2007-08-03 09:55

卧龙孔明

等　级：贵宾
威　望：59
帖　子：3872
专家分：684
注　册：2006-10-13

第 18 楼