目录
题目：
题目描述
一个正整数一般可以分为几个互不相同的自然数的和，如
3=1+2
，
4=1+3
，
5
＝1+4=2+3
，
6=1+5
＝2+4
。
现在你的任务是将指定的正整数
n
n
分解成若干个互不相同的自然数的和，且使这些自然数的乘积最大。
输入格式
只一个正整数
n
，（
3≤
n
≤10000
）。
输出格式
第一行是分解方案，相邻的数之间用一个空格分开，并且按由小到大的顺序。
第二行是最大的乘积。
思路：
ln(a)+ln(b)=ln(a×b)。
这个性质很好的解决了这个问题。问题转化：
给定物品价值和体积均为1 2 3 ……n,背包容量为n，问乘积最大的选择。
转化方程：
for(int i = 1;i <= n;i++)
for(int j = n;j >= i;j--)
if(dp[j] < dp[j-i]+log(i))
dp[j] = dp[j-i]+log(i);//注意dp是double型如果记录拆分情况？另设数组divs，divs[i]表示当容量为i是最后一个物品。
比如选择了dp[j] = dp[j-i]+log(i);这时候divs[j]=i。
这样下个物品就是容量为j-divs[j]的情况。
所以有循环：
for(int i = n;i > 0;i = i - divs[i]) ans.push_back(divs[i]);
for(int i = ans.size()-1;i >= 0;i--){
cout<<ans[i]<<' ';
}
cout<<endl;因为是大数乘，需要大数模板函数：
https://blog.csdn.net/m0_50623076/article/details/109233382
模拟乘法：
void mul(int x){
for(int i = 0;i < 1000;i++) a[i]*=x;
int carry = 0;
for(int i = 0;i < 1000;i++){
a[i]+=carry;
carry=a[i]/10;
a[i]%=10;
}
}
代码：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
#include<queue>
#include<map>
#include<cstdio>
#include<cmath>
#include<stdlib.h>
using namespace std;
typedef long long ll;
const int maxn = 1e4+50;
double dp[maxn];
int divs[maxn];
int a[1005];
void mul(int x){
for(int i = 0;i < 1000;i++) a[i]*=x;
int carry = 0;
for(int i = 0;i < 1000;i++){
a[i]+=carry;
carry=a[i]/10;
a[i]%=10;
}
}
int main(){
int n;
cin >> n;
for(int i = 1;i <= n;i++)//01背包
for(int j = n;j >= i;j--)
if(dp[j] < dp[j-i]+log(i)){
dp[j] = dp[j-i]+log(i);
divs[j] = i;
}
vector<int>ans;
for(int i = n;i > 0;i = i - divs[i]) ans.push_back(divs[i]); //记下所选数
for(int i = ans.size()-1;i >= 0;i--){
cout<<ans[i]<<' ';
}
cout<<endl;
a[0] = 1;
for(int i = 0;i < ans.size();i++) mul(ans[i]);//大数乘法函数
int p = 1000;
while(!a[p]) p--;//输出最大数
for(;p >= 0;p--) cout<<a[p];
cout<<endl;
return 0;
}