整数拆分问题
给一个数n，你可以将这个数拆成任意个整数，现在我们想知道在所有的拆分方式中 拆出来的所有的数的积 的最大值。
如 n = 6, 可以拆成
3 * 3 = 9
2 * 4 = 8
2 * 2 * 2 = 8
1 * 1 * 4 = 4
1 * 1 * 2 * 2 = 4
...
最大值为9
怎么进行拆分啊？
[解决办法]
我的基本结论是(没有证明),对于数n,如果可拆成几个相等的数，当每个数为3时，其乘积最大。
1个基本的事实，在边长相等的情况下，正方形体积最大。故拆分的几个数应该尽量大小相同。
例如：
6=2×3，可拆成几个2或者几个3，拆成几个3其乘积最大。
60是2，3，4，5，6的公倍数，可拆成30个2，或者20个3，15个4，或者12个5，或者10个6.计算可知，拆成20个3，其乘积最大。
容易看出，若1个数是n=4K， 则这个数可以拆成 2K个2，或者K个4，其乘积总是相同的，因为2^(2k)=4^k,
推测，若一个数是m-1,m,m+1的倍数，且拆分为K个m时，其乘积最大，则m为峰值，m-1和m+1都没有m好。
因为 2^2k=4^k,其峰值应该是3。
请数学好的同学来证明。
[解决办法]
[解决办法]
高中都学过的函数可以证明，设 其中一个数为x，总和为a，
则，拆分的另一个数为a-x，则所得乘积y=x(a-x)
讨论函数的增减性，画图，是个倒着的抛物线，交x轴于0,和a，则最高点为a/2
涉及到取整数问题，选取最接近a/2的数
[解决办法]
顺便写了一个，见笑了
- C/C++ code
/**给一个数n，你可以将这个数拆成任意个整数，现在我们想知道在所有的拆分方式中 拆出来的所有的数的积 的最大值。如 n = 6, 可以拆成 3 * 3 = 92 * 4 = 82 * 2 * 2 = 81 * 1 * 4 = 41 * 1 * 2 * 2 = 4...最大值为9 */#include <iostream>using namespace std;#define M 5/*要划分的整数*/#define N 11/*要划分成的整数*/static int a[M] = {1,2,5,7,9};/*根据上面的给值得到划分后最大的乘积*/int get_max_product(){ int max_num = 0; int dp[N + 1] = {0}; for (int i = 0;i < N + 1;i++) { dp[i] = 1; } for (int i = 0;i < M;i++) { for (int j = a[i];j < N + 1;j++) { dp[j] = dp[j - a[i]] * a[i]; } if (max_num < dp[N]) { max_num = dp[N]; } } return max_num;}int main(){ cout << get_max_product() << endl; /** * 2 * 2 * 2 * 2 * 2 * 1 = 32 * 5 * 5 * 1 = 25 * 7 * 2 * 2 = 28 * 得证，最大为32 */ return 0;}
[解决办法]
算法的优化版本，不采用动态规划空间
- C/C++ code
int get_max_product_2(){ int max_num = 0; for (int i = 0;i < M;i++) { int temp_n = N; int temp_num = 1; for (int j = i;j >= 0;j--) { temp_num *= int(pow(a[j],temp_n / a[j] * 1.0)); temp_n %= a[j]; } if (temp_num > max_num) { max_num = temp_num; } } return max_num;}