将数字拆分为总和组件

Question

是否有一种有效的算法可以将一个数字拆分成N子部分,以便数字的总和加起来与原始数字相符,最小值是什么？例如,如果我想将50分成7个子部分,并且基数最小值为2,我可以做10,5,8,2,3,5,17(以及任何其他数量的组合).我想将数字保持为整数,并且相对随机,但我不确定如何有效地生成总和为原始的数字,并且不包括低于给定最小值的数字.有什么建议？

编辑 - 只是为了复制/粘贴我的评论,整数不一定是唯一的,但我希望每次都避免所有这些(例如50分为10个相同大小)的相同大小.

Answer 1

这是一个算法:

1. 分N由m哪里N是你的号码,m是小节的数量.
2. 将结果舍入到最接近的值,并将该值分配给所有子部分.
3. 在每个子部分中添加一个,直到值相加N.此时如果N是50并且m是7,那么你将有8,7,7,7,7,7,7
4. 从0到I m-1,步长为2,并在-(currentValue-base)和之间添加一个随机数currentValue-base.将该数字的倒数添加到其相邻存储桶中.如果您有一个奇数个桶,那么在最后一个桶上,而不是将该数字的倒数添加到其相邻桶中,以类似于上面步骤2和3的分布式方式将其添加到所有其他桶中.

性能:第1步是O(1)步骤2,3和4 O(m),总的来说就是这样O(m).

Answer 2

您可以通过从数字中减去最小次数N,生成N个子部分并添加最小值,轻松删除最小要求.在您的示例中,问题减少为将36拆分为7个整数,并且您已经给出了拆分8,3,6,0,1,3,15.

解决方案的其余部分取决于"相对随机"要求的性质.对于一些最小的随机性,考虑在0和未分裂部分之间顺序选择数字(例如,首先在0和36之间,获得8,然后在0和28之间,获得3,依此类推7次).如果这还不够,您首先需要定义随机性.