立方数最小和问题

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

不回复咋还不让看呀

账号		自动登录	找回密码
密码			欢迎注册

[擂台] 立方数最小和问题