最大化产生给定和"k"的不同数字数量

Question

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

给定一个正整数 k，找到总和为 k 的最大不同正整数个数。例如，6 = 1 + 2 + 3，因此答案应为 3，而不是 5 + 1 或 4 + 2，这两种情况都只有 2 个不同的正整数。

我首先想到的是要找到子问题。因此，为了找到 k 的最大和，我们需要找到小于 k 的值的最大和。所以我们必须遍历值 1 -> k 并找到这些值的最大和。

让我困惑的是如何制定一个公式。我们可以将 M(j) 定义为总和为 j 的最大不同正整数个数，但我该如何实际编写它的公式呢？

我的思路是否正确，有人能够解释一下如何逐步解决这个问题吗？

- template boy

---

我认为动态规划并不是必要的。只需找到最大的整数n，使得n(n+1)/2 <= k -- 基本上是重新排列，解出n并向下取整。n(n+1)/2是1+2+3+...+n的总和，为了使总和为k，您只需将n替换为k-n(n-1)/2。 - moreON

这个问题有一个封闭形式的解决方案，比其他任何已发布的解决方案都更有效。我曾经发布过它一段时间，但人们不理解它并且投了反对票，所以我把它删除了。你只能满足于一个效率较低的解决方案。 - Tom Karzes

你需要做的就是找到小于目标值的最大三角形数。该三角形数的顺序即为答案。 - Jasen

如果不同的正整数是从输入数组中获取的，并且它们不是连续的正整数，那么这将是一个动态规划问题。因此，我必须怀疑您是否搞砸了问题描述。 - user3386109

提示：请在纸上解决1到20的数字问题。你能描述出模式吗？ - Colonel Panic

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;
    }
}

- Nayuki

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

- uh oh somebody needs a pupper

---

如果你有一个常数时间的解决方案，为什么要使用动态规划呢？非常好。 - gnasher729

从数学SE找到一个完美的答案，干得好！此外，“处理浮点数的缺点”根本不是缺点。可以通过使用分数和向下取整平方根将其表达为整数算法。 - Nayuki

Answer 3

最小的可以表示为i个不同正整数之和的数字是1 + 2 + 3 + ... + i = i(i+1)/2，也被称为第i个三角形数T[i]。

设i 是最大的满足 T[i] ≤ k 的i值。

那么我们可以用i个不同的正整数来表示k的和：

1 + 2 + 3 + ... + (i-1) + (i + k - T[i])

请注意，最后一项大于或等于i(因此与其他整数不同)，因为k >= T[i]。

另外，不可能表示k为i + 1个不同正整数的和，因为最小的i+1个不同正整数的和是T[i+1] > k，这是由于我们选择的i导致的。

所以你的问题等价于找到最大的i使得T[i] <= k。

解决这个问题的方法如下：

 i = floor((-1 + sqrt(1 + 8k)) / 2)

[参考链接: https://math.stackexchange.com/questions/1417579/largest-triangular-number-less-than-a-given-natural-number ]

您也可以编写一个简单的程序，迭代三角形数，直到找到第一个大于k的三角形数：

def uniq_sum_count(k):
    i = 1
    while i * (i+1) <= k * 2:
        i += 1
    return i - 1

for k in xrange(20):
    print k, uniq_sum_count(k)

- Paul Hankin

---

你知道这是一个关于C语言的问题，而不是Python的问题，对吧？ - Tom Karzes

Answer 4

我认为你只需要检查是否符合条件 1 + ... + n > k。如果是这样，打印出 n-1。

因为如果你找到了最小的 n 使得 1 + ... + n > k，那么 1 + ... + (n-1) <= k。所以添加额外的值，比如说 E，到 (n-1) 上，然后有 1 + ... + (n-1+E) = k。

因此，n-1 是最大值。

请注意：1 + ... + n = n(n+1) / 2

#include <stdio.h>

int main()
{
  int k, n;
  printf(">> ");
  scanf("%d", &k);
  for (n = 1; ; n++)
    if (n * (n + 1) / 2 > k)
      break;
  printf("the maximum: %d\n", n-1);
}

或者您可以制作 M(j)。

int M(int j)
{
  int n;
  for (n = 1; ; n++)
    if (n * (n + 1) / 2 > j)
      return n-1; // return the maximum.
}

- Yonggoo Noh

Answer 5

嗯，这个问题可能可以不用动态规划解决，但我试图以动态规划的方式来看待它。

提示：当你想要解决一个动态规划问题时，你应该看到何时情况是“重复”的。在这里，由于从数字k的角度来看，如果我先减去1再减去3或者先减去3再减去1都没有关系；所以我说“让我们按升序减去它”。 现在，什么是重复的？好的，我的想法是我想从数字k开始，不断地从不同的元素中减去它，直到得到零。因此，如果我达到了一个剩余数字和我使用的最后一个不同数字相同的情况，那么这种情况就是“重复”的：

#include <stdio.h>

bool marked[][];
int memo[][];

int rec(int rem, int last_distinct){
    if(marked[rem][last_distinct] == true) return memo[rem][last_distinct]; //don't compute it again
    if(rem == 0) return 0; //success
    if(rem > 0 && last > rem - 1) return -100000000000; //failure (minus infinity)
    int ans = 0;
    for(i = last_distinct + 1; i <= rem; i++){
        int res = 1 + rec(rem - i, i); // I've just used one more distinct number
        if(res > ans) ans = res;
     }
    marked[rem][last_distinct] = true;
    memo[rem][last_distinct] = res;
    return res;
}

int main(){
   cout << rec(k, 0) << endl;
   return 0;
}

时间复杂度为O(k^3)

- A. Mashreghi

Answer 6

虽然不完全清楚在获得最大离散数列方面可能存在哪些限制，但如果您能够通过传递一个简单的数组来保存离散数，并在函数中保持运行总和，可以简化该过程。例如，将数组a与当前的j一起传递到函数中，并返回组成数组中总和的元素数量，可以使用以下代码完成：

int largest_discrete_sum (int *a, int j)
{
    int n, sum = 0;
    for (n = 1;; n++) {
        a[n-1] = n, sum += n;
        if (n * (n + 1) / 2 > j)
            break;
    }
    a[sum - j - 1] = 0;  /* zero the index holding excess */
    return n;
}

将它放在一个简短的测试程序中会像这样：

#include <stdio.h>

int largest_discrete_sum(int *a, int j);

int main (void) {

    int i, idx = 0, v = 50;
    int a[v];

    idx = largest_discrete_sum (a, v);
    printf ("\n largest_discrete_sum '%d'\n\n", v);
    for (i = 0; i < idx; i++)
        if (a[i])
            printf (!i ? "  %2d" : " +%2d", a[i]);
    printf (" = %d\n\n", v);
    return 0;
}

int largest_discrete_sum (int *a, int j)
{
    int n, sum = 0;
    for (n = 1;; n++) {
        a[n-1] = n, sum += n;
        if (n * (n + 1) / 2 > j)
            break;
    }
    a[sum - j - 1] = 0;  /* zero the index holding excess */
    return n;
}

使用示例/输出

$ ./bin/largest_discrete_sum

 largest_discrete_sum '50'

   1 + 2 + 3 + 4 + 6 + 7 + 8 + 9 +10 = 50

如果我在离散值选择方面错过了某个限制条件，我深表歉意，但是以这种方式进行处理，您可以确保获得与您的总和相等的最大离散值数量。如果您有任何问题，请告诉我。

- David C. Rankin