求能穷举"不是9个自然数立方和"的整数的算法,该怎么处理
求能穷举"不是9个自然数立方和"的整数的算法
这里说的自然数包括0。
我的算法如下:
1.把小于n的立方和数字列出来，例如0,1,8,27,64,125，我认为有m个立方和数字小于n。
2.对于n，查看上述列表，从大到小应用表中元素做除法。
例如对于269，我知道269=125*2+8*2+1*3。可以用少于9个立方和数来表示。
但是我发现这种贪心的算法会有遗漏。比如 50=6*2^3+2*1^3+1*0^3，用贪心的方法只能得到50=1*3^3+2*2^3+7*1^3，大于9个数
如何设计这样的一个算法呢? 还请大虾指点啊！
------解决方案--------------------
不知道n有多大，小的话整数背包可以试试
------解决方案--------------------
贪心法没设计好吧，设计好了穷举时候不可能漏的
这里说的自然数包括0。
我的算法如下:
1.把小于n的立方和数字列出来，例如0,1,8,27,64,125，我认为有m个立方和数字小于n。
2.对于n，查看上述列表，从大到小应用表中元素做除法。
例如对于269，我知道269=125*2+8*2+1*3。可以用少于9个立方和数来表示。
但是我发现这种贪心的算法会有遗漏。比如 50=6*2^3+2*1^3+1*0^3，用贪心的方法只能得到50=1*3^3+2*2^3+7*1^3，大于9个数
如何设计这样的一个算法呢? 还请大虾指点啊！
------解决方案--------------------
不知道n有多大，小的话整数背包可以试试
------解决方案--------------------
贪心法没设计好吧，设计好了穷举时候不可能漏的