Максимальное количество различных чисел, которые дают заданную сумму '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 - таким образом, это невозможно.

В самом деле, если мы будем использовать именно п различные положительные целые числа, то наименьшее число с такой суммой 1 + 2 + ... + п = п (п + 1)/2 , Решая квадратичную форму, имеем M (k) составляет приблизительно sqrt (2 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

Наименьшее число, которое может быть представлено в виде суммы i различных положительных целых чисел 1 + 2 + 3 + ... + i = i(i+1)/2, иначе известный как «i го треугольного числа, T[i].

Позвольте i быть таким, чтобы T[i] было самым большим треугольным числом, которое меньше или равно вашему k.

Тогда мы можем представить k как сумма i различных натуральных чисел:

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]

Вы также можете написать простую программу для перебора треугольных чисел, пока вы не найдете первых больше, чем к:

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 3

Я думаю, вы просто проверяете, 1 + ... + n > k. Если да, напечатайте n-1.

Потому что, если вы найдете наименьшее n как 1 + ... + n > k, то 1 + ... + (n-1) <= k. поэтому добавьте дополнительную стоимость, скажем E, до (n-1), затем 1 + ... + (n-1+E) = k.

Следовательно n-1 - это максимум.

Обратите внимание, что: 1 + ... + п = п (п + 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. 
} 

Answer 4

Ну, проблема может быть решена без динамического программирования, однако я попытался взглянуть на нее динамическим способом программирования.

Совет: когда вы хотите решить проблему динамического программирования, вы должны видеть, когда ситуация повторяется. Здесь, поскольку с точки зрения числа 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; 
} 

Трудоемкость О (к^3)

Answer 5

Хотя не совсем ясно, какие ограничения могут быть связаны с тем, как вы достигаете наибольшей дискретной серии чисел, но если вы в состоянии, передаете простой массив для хранения дискретных чисел и сохраняете текущую сумму в своих функциях может упростить процесс.Например, передача массива 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 

Прошу прощения, если я пропустил ограничение на выбор дискретных значений где-то, но, приближаясь таким образом, вам гарантировано получить наибольшее количество дискретных значений, которое будет равно вашей сумме. Дайте знать, если у вас появятся вопросы.

Answer 6

Другие ответы правильно сделать вывод, что данная проблема в основном это суммирование:

Однако это на самом деле может быть упрощена

В коде это выглядит так: 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}