论坛 › 编程擂台 › 立方数最小和问题

gxqcn 发表于 2008-5-4 21:52:53

当限制正负符号各半时，其实比不限制时更简单些。

限制时，只需搜索长度一半的数据组合，并以倒序为宜，使其指定指数次幂和为定值即可。
如果指定最大的数 N 必含在其中，则仅需搜索长度 N/2-1 的其它数据组合。

gxqcn 发表于 2008-5-4 22:04:16

晚饭后到医院挂盐水，刚刚回来。
明天再看能否抽空写个简陋的程序运行下。

无心人 发表于 2008-5-4 22:05:50

:)

还没好啊
够粘手的啊

gxqcn 发表于 2008-5-4 22:10:34

医生开的两天的药，
考虑到今天要上班，本想下班后就近到附近的社区卫生所去挂，
但对方总扯些理由，一会儿说缺输液记录单，一会儿又说少药水，
只得赶到昨天去的那家大医院去。。。:@

mathe 发表于 2008-5-5 07:19:34

这是因为复杂度太高了，我使用的是动态规划，而不是搜索的方法

无心人 发表于 2008-5-5 07:56:40

小医院怕担责任
不是自己的处方都不愿意输

mathe 发表于 2008-5-5 08:07:40

不会吧，我们这边社区医院我觉得除了替人挂盐水就没什么其它可取的了

mathe 发表于 2008-5-5 09:17:16

正负个一半的情况由于需要太多空间，很难计算，我通过一种方法计算了一个下界
将80个数划分成小的50个和大的30个，
首先计算第一组中使用了k个正号（50-k个负号),和为x的情况是否出现(0<=x)(如果保存计数，那么内存空间会不够）
然后计数后面30个数中同样使用了k个正号(30-k个负号)和也为x的情况的数目。累加这些数目（在第一组对应情况出现时)，通过8分钟计算得到49596436组结果。也就是结果不小于这个数

mathe 发表于 2008-5-5 10:34:58

上面算错了，上面计算出来的实际上是正负分别为30和50情况的数目。而对于各自一半的，数目还要多，是
192314030

shshsh_0510 发表于 2008-5-5 10:35:27

不回复咋还不让看呀

查看完整版本: 立方数最小和问题