The maximum number of different numbers that give a given sum k,

Question

I need help with this dynamic programming problem.

For a positive integer k find the maximum number of different positive integers whose sum is k . For example, 6 = 1 + 2 + 3, so the answer will be 3, not 5 + 1 or 4 + 2, which will be 2.

The first thing I think about is that I have to find a subtask. So, to find the maximum amount for k , we need to find the maximum amount for values ​​less than k . Thus, we must iterate over the values 1 -> k and find the maximum sum for these values.

What bothers me is how to make a formula. We can define M(j) as the maximum number of different values ​​that add up to j , but how can I write a formula for it?

Is my logic that I'm still true, and can anyone explain how to do this step by step?

Answer 1

No dynamic programming is required. 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 are how far we can go. If we use ten numbers, the sum will be at least 1 + 2 + 3 + ... + 10 = 55, which is more than 50 - so this is not possible.

Indeed, if we use exactly n different natural numbers, then the lowest number with such a sum is 1 + 2 + ... + n = n (n + 1) / 2. Solving the quadratic formula, we have M (k) approximately sqrt (2 k ).

Thus, the algorithm should take the number k, subtract 1, 2, 3, etc., until we can no longer, and then reduce by 1. The algorithm in C:

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

Answer 2

Other answers correctly conclude that the problem lies mainly in this summation:

However, this can be simplified to

In the code, it looks like this: 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, we find the maximum positive integers that can form its sum, URL (version: 2012-03 -22): https://math.stackexchange.com/q/123128}

Answer 3

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

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

Then we can represent k as the sum of i different natural numbers:

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

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

In addition, it is impossible to represent k as the sum of i+1 different positive integers, since the smallest number is that the sum of i+1 different natural numbers T[i+1] > k due to the way we chose i .

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

This solution:

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

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

You can also write a simple program to iterate over triangular numbers until you find the first value greater than 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) 

Answer 4

I think you are just checking to see if there is 1 + ... + n > k . If yes, type n-1 .

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

Therefore, n-1 is the maximum.

Note that: 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 do M(j) .

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

Answer 5

Well, the problem can be solved without dynamic programming, however I tried to look at it in dynamic programming.

Tip. When you want to solve the problem of dynamic programming, you should see when the situation recurs. Here, since from the point of view of the number k it does not matter if, for example, I subtract 1 first, then 3 or the first 3, and then 1; I say that "let him subtract from it in ascending order." Now, what is repeated? Well, the idea is that I want to start with the number k and subtract it from the individual elements until I get to zero. So, if I get to the situation where the remaining number and the last separate number that I used are the same, the situation "repeats":

 #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 complexity of time is O (k ^ 3)

Answer 6

Although it is not clear what limitations may be related to how you achieve the largest discrete series of numbers, but if you are able to, passing a simple array to store discrete numbers and storing the current amount in your function can simplify the process. For example, passing an array a long with the current j to the function and returning the number of elements that make up the sum in the array can be performed using the following:

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

Combining in a short test program will look like this:

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

Usage / Output Example

 $ ./bin/largest_discrete_sum largest_discrete_sum '50' 1 + 2 + 3 + 4 + 6 + 7 + 8 + 9 +10 = 50 

I apologize if I missed the restriction on the choice of discrete values ​​somewhere, but, approaching in this way, you are guaranteed to get the largest number of discrete values ​​that will be equal to your sum. Let me know if you have any questions.