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

Question

我需要帮助解决这个动态规划问题。

Given a positive integer k, find the maximum number of distinct positive integers that sum to k. For example, 6 = 1 + 2 + 3 so the answer would be 3, as opposed to 5 + 1 or 4 + 2 which would be 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(2k)。

因此算法是取数 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;
    }
}