将数字分解成3部分即可找到最大和
给出一个数字。我们的任务是将数字三倍地除以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