Question

17个数字，每个数字的范围是0-800,17个数字相加等于2187的组合有多少种，如果可以告诉我怎么算的奖赏50？

对于这个问题我希望能有高手来帮我算出来并且具体的过程讲解下，谢谢

Answer 1

两种途径。

第一是枚举，规模太大，显然不可能在有限时间内完成。

第二种是动态规划算法，可以快速求得结果，但是无法列出所有组合。

根据题意，只能选择第二种方法。

结果是，一共有 5099730881649849682367301717604 种组合。

这大约相当于 500万亿亿亿个。计算耗时约2秒钟。

附：计算结果和fortran代码（算法详见注视，绿色文字）

追答

和值的问题，没有直接公式计算方法。

楼上所答，纯属误人子弟。

补充一下：

若是范围在0到800，17个数不允许重复（即为互不相等的自然数）

则一共有 23349056625053475455074252 种组合。大约是 23亿亿亿个。

代码只需要稍作修改，屏蔽掉最后一种次级递归方案。如下图：

Answer 2

第一个数字有从0到800种选法，即有801种选法，第二个数字有801一1种选法，即800种选法，依此类推，共有801x800x799x……x786x785种组合。谢谢。