求出给定和k的不同数的最大值

I need help with this dynamic programming problem.

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

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相对应的正整数的最大值，例如，6 = 1 + 2 + 3，所以答案是3，而不是5 + 1或4 + 2 = 2。

The first thing I think of is that I have to find a subproblem. So to find the max sum for k, we need to find the max sum for the values less than k. So we have to iterate through the values 1 -> k and find the max sum for those values.

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

What confuses me is how to make a formula. We can define M(j) as the maximum number of distinct values that sum to j, but how do I actually write the formula for it?

让我困惑的是如何制作一个公式。我们可以把M(j)定义为j的最大不同的值，但是我怎么写出它的公式呢?

Is my logic for what I have so far correct, and can someone explain how to work through this step by step?

我的逻辑是正确的吗?有人能解释如何一步一步地完成吗?

6 个解决方案

#1

No dynamic programming is need. Let's start with an example:

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

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)

Nine numbers is as far as we can go. If we use ten numbers, the sum would be at least 1 + 2 + 3 + ... + 10 = 55, which is greater than 50 - thus it is impossible.

9个数字是我们能做到的。如果我们用10个数字，总和至少是1 + 2 + 3 +…+ 10 = 55，大于50，这是不可能的。

Indeed, if we use exactly n distinct positive integers, then the lowest number with such a sum is 1+2+...+n = n(n+1)/2. By solving the quadratic, we have that M(k) is approximately sqrt(2k).

实际上，如果我们用n个不同的正整数，那么这个和的最小值就是1+2+…+ n = n(n + 1)/ 2。通过解这个二次方程，我们得到M(k)近似等于√2k。

Thus the algorithm is to take the number k, subtract 1, 2, 3, etc. until we can't anymore, then decrement by 1. Algorithm in C:

所以算法就是取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;
    }
}

#2

The other answers correctly deduce that the problem essentially is this summation:

另一个答案正确地推断出问题本质上是这个总和:

However this can actually be simplified to

然而，这实际上可以简化为。

In code this looks like : floor(sqrt(2.0 * k + 1.0/4) - 1.0/2)

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

The disadvantage of this answer is that it requires you to deal with floating point numbers.

这个答案的缺点是它要求你处理浮点数。

^{Brian M. Scott (https://math.stackexchange.com/users/12042/brian-m-scott), Given a positive integer, find the maximum distinct positive integers that can form its sum, URL (version: 2012-03-22): https://math.stackexchange.com/q/123128}

给定一个正整数，找到可以构成其和的最大不同正整数，URL(版本:2012-03-22):https://math.stackexchange.com/q/123128。

#3

The smallest number that can be represented as the sum of i distinct positive integers is 1 + 2 + 3 + ... + i = i(i+1)/2, otherwise known as the i'th triangular number, T[i].

最小的数可以表示为1 + 2 + 3 +…i = i(i+1)/2，也称为i'th三角数T[i]。

Let i be such that T[i] is the largest triangular number less than or equal to your k.

假设T[i]是小于或等于k的最大三角形数。

Then we can represent k as the sum of i different positive integers:

然后我们可以将k表示为不同正整数的和:

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

Note that the last term is greater than or equal to i (and therefore different from the other integers), since k >= T[i].

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

Also, it's not possible to represent k as the sum of i+1 different positive integers, since the smallest number that's the sum of i+1 different positive integers is T[i+1] > k because of how we chose i.

也不可能把k表示为i+1不同正整数的和，因为最小的数是i+1不同正整数的和等于T[i+1] > k因为我们选择i的方式。

So your question is equivalent to finding the largest i such that T[i] <= k.

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

That's solved by this:

解决的:

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

[derivation here: https://math.stackexchange.com/questions/1417579/largest-triangular-number-less-than-a-given-natural-number ]

(来源:https://math.stackexchange.com/questions/1417579/largest-triangular-number-less-than-a-given-natural-number]

You could also write a simple program to iterate through triangular numbers until you find the first larger than k:

你也可以编写一个简单的程序来遍历三角形数字，直到你找到第一个大于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)

#4

I think you just check if 1 + ... + n > k. If so, print n-1.

我想你应该检查一下1 +…+ n > k，如果是，打印n-1。

Because if you find the smallest n as 1 + ... + n > k, then 1 + ... + (n-1) <= k. so add the extra value, say E, to (n-1), then 1 + ... + (n-1+E) = k.

因为如果你发现最小的n等于1 +…+ n > k，然后1 +…+ (n-1) <= k，因此添加额外的值，比如E，到(n-1)，然后1 +…+(n - 1 + E)= k。

Hence n-1 is the maximum.

因此n-1是最大值。

Note that : 1 + ... + n = n(n+1) / 2

注意: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);
}

Or you can make M(j).

或者你可以做M(j)

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

#5

Well the problem might be solved without dynamic programming however i tried to look at it in dynamic programming way.

如果没有动态规划，问题就可以解决了，但是我尝试用动态编程的方式来研究它。

Tip: when you wanna solve a dynamic programming problem you should see when situation is "repetitive". Here, since from the viewpoint of the number k it does not matter if, for example, I subtract 1 first and then 3 or first 3 and then 1; I say that "let's subtract from it in ascending order". Now, what is repeated? Ok, the idea is that I want to start with number k and subtract it from distinct elements until I get to zero. So, if I reach to a situation where the remaining number and the last distinct number that I have used are the same the situation is "repeated":

提示:当你想要解决一个动态的编程问题时，你应该看看什么时候情况是“重复性的”。这里，因为从数字k的角度来看，如果我先减去1然后再减去3或3，然后再减去1;我说"我们用升序减去它"现在,重复是什么?好的，这个想法是我想从k开始，从不同的元素中减去它直到我得到0。所以，如果我碰到一个情况，剩下的数和我用过的最后一个数字是相同的情况是“重复的”:

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

The time complexity is O(k^3)

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

#6

Though it isn't entirely clear what constraints there may be on how you arrive at your largest discrete series of numbers, but if you are able, passing a simple array to hold the discrete numbers, and keeping a running sum in your functions can simplify the process. For example, passing the array a long with your current j to the function and returning the number of elements that make up the sum within the array can be done with something like this:

虽然还不完全清楚您是如何到达最大的离散数字序列的，但是如果您能够，通过一个简单的数组来保存离散的数字，并且在函数中保持一个运行的和可以简化这个过程。例如，将当前j的数组传递给函数，并返回构成数组中sum的元素个数，可以这样做:

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

Putting it together in a short test program would look like:

把它放在一个短的测试程序中看起来是这样的:

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

Example Use/Output

使用/输出示例

$ ./bin/largest_discrete_sum

 largest_discrete_sum '50'

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

I apologize if I missed a constraint on the discrete values selection somewhere, but approaching in this manner you are guaranteed to obtain the largest number of discrete values that will equal your sum. Let me know if you have any questions.

如果我在某个地方错过了对离散值选择的约束，我很抱歉，但是以这种方式接近，您就可以得到最大数量的离散值，这将等于您的和。如果你有什么问题，请告诉我。