번호가 제공됩니다. 우리의 임무는 숫자를 n/2, n/3, n/4로 세 번 나누고 숫자를 세 부분으로 나누어 만들 수 있는 최대 합을 찾는 것입니다.
예를 들어, 50은 {25, 16, 12}로 나눌 수 있습니다. 이제 각 집합 {25, 16, 12}를 다시 세 부분으로 나누는 식입니다. 나눗셈을 3회까지 완료한 후 합산하여 최대값을 구합니다.
이 프로그램은 재귀적 방식으로 풀 수 있지만 재귀적 접근 방식에서는 동일한 결과를 여러 번 찾아야 하므로 동적 프로그래밍 방식을 사용하고 이전에 계산된 데이터를 테이블에 저장하면 시간.
입력 및 출력
Input: Let the given number is 12. Output: The answer is 13. At first divide the 12 as (12/2 + 12/3 + 12/4) = 6 + 4 + 3 = 13. now divide 6 into three parts (6/2 + 6/3 + 6/4) = 3 + 2 + 1 = 6. If we divide the 4 and 3, we can get maximum 4 from them. From all values the maximum is 13.
알고리즘
maxBreakSum(n)
입력: 주어진 번호입니다.
출력: 깨기 후 최대 합계입니다.
Begin define sums array of size n+1 sums[0] := 0, sums[1] := 1 for i in range 2 to n, do sum[i] := maximum of i and (sums[i/2] + sums[i/3] + sums[i/d]) done return sums[n] End
예
#include<iostream> #define MAX 1000000 using namespace std; int max(int a, int b) { return (a>b)?a:b; } int maxBreakSum(int n) { int sumArr[n+1]; sumArr[0] = 0, sumArr[1] = 1; //for number 0 and 1, the maximum sum is 0 and 1 respectively for (int i=2; i<=n; i++) //for number 2 to n find the sum list sumArr[i] = max(sumArr[i/2] + sumArr[i/3] + sumArr[i/4], i); //divide number by 2, 3, 4 return sumArr[n]; } int main() { int n; cout << "Enter a number: "; cin >> n; cout << "Maximum sum after breaking: " << maxBreakSum(n); }
출력
Enter a number: 12 Maximum sum after breaking: 13