이 동적 프로그래밍 문제에 대한 도움이 필요합니다.
양의 정수가 주어지면
k합계가되는 고유 양의 정수의 최대 수를 찾습니다k. 예를 들어 6 = 1 + 2 + 3이므로 답은 3이되고, 5 + 1 또는 4 + 2는 2가됩니다.
가장 먼저 생각하는 것은 하위 문제를 찾아야한다는 것입니다. 따라서에 대한 최대 합계 k를 찾으려면보다 작은 값에 대한 최대 합계를 찾아야합니다 k. 따라서 값을 반복하고 해당 값에 1 -> k대한 최대 합계를 찾아야합니다.
나를 혼란스럽게하는 것은 공식을 만드는 방법입니다. M(j)합계가에 해당하는 고유 값의 최대 수로 정의 할 수 j있지만 실제로 공식을 어떻게 작성합니까?
내가 지금까지 가지고있는 것에 대한 내 논리가 정확하고 누군가이 단계별로 작업하는 방법을 설명 할 수 있습니까?
동적 프로그래밍이 필요하지 않습니다. 예를 들어 보겠습니다.
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)
9 개의 숫자는 우리가 할 수있는 한 멀리 있습니다. 10 개의 숫자를 사용하면 합계는 적어도 1 + 2 + 3 + ... + 10 = 55가되며 50보다 큽니다. 따라서 불가능합니다.
실제로, 정확히 n 개의 고유 한 양의 정수를 사용한다면 , 그러한 합계를 가진 가장 낮은 숫자는 1 + 2 + ... + n = n ( n +1) / 2입니다. 2 차를 풀면 M ( k )이 대략 sqrt (2 k ) 임을 알 수 있습니다 .
따라서 알고리즘은 숫자 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;
}
}
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다