最大化产生给定总和'k'的不同数字的计数

Question

我需要这个动态编程问题的帮助.

给定正整数k,找到求和的不同正整数的最大数量k.例如,6 = 1 + 2 + 3,因此答案为3,而5 + 1或4 + 2则为2.

我想到的第一件事是我必须找到一个子问题.因此,要找到最大总和k,我们需要找到小于的最大值k.所以我们必须迭代这些值1 -> k并找到这些值的最大总和.

令我困惑的是如何制作一个公式.我们可以定义M(j)为总和的最大不同值的数量j,但我如何实际为其编写公式？

到目前为止,我的逻辑是否正确,有人可以解释如何逐步完成这项工作吗？

Answer 1

不需要动态编程.让我们从一个例子开始:

50 = 50
50 = 1 + 49
50 = 1 + 2 + 47  (three numbers)
50 = 1 + 2 + 3 + 44  (four numbers)
50 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 14  (nine numbers)

我们可以追溯到九个数字.如果我们使用十个数字,则总和将至少为1 + 2 + 3 + ... + 10 = 55,这大于50 - 因此这是不可能的.

实际上,如果我们使用恰好n个不同的正整数,那么具有这样的和的最小数是1 + 2 + ... + n = n(n + 1)/ 2.通过求解二次方,我们得到M(k)大约是sqrt(2 k).

因此算法是取数k,减去1,2,3等,直到我们不能再减去,然后递减1. C中的算法:

int M(int k) {
    int i;
    for (i = 1; ; i++) {
        if (k < i) return i - 1;
        else k -= i;
    }
}

Answer 2

其他答案正确地推断出问题基本上是这个总和:

然而,这实际上可以简化为

在代码中,这看起来像: floor(sqrt(2.0 * k + 1.0/4) - 1.0/2)

这个答案的缺点是它需要你处理浮点数.

^{Brian M. Scott(https://math.stackexchange.com/users/12042/brian-m-scott),给定一个正整数,找到可形成其总和的最大不同正整数,URL(版本:2012-03 -22):https://math.stackexchange.com/q/123128}