最优分解问题，不知道我的算法思想对不对，反正我写好的这个程序提交到判题系统上是错误的

[rob2468]

最优分解问题

问题描述：

设n是一个正整数。现在要求将n分解为若干个互不相同的自然数的和，且使这些自然数的乘积最大。

你的任务是对于给定的正整数n，编程计算最优分解方案。
输入：
输入有若干行，每一行上是一个整数n，（|n|£50）。
输出：
对输入中的每个整数n，如果是无效输入，那么输出“invalid input!”，否则输出最优分解方案，以从小到大的顺序排列，中间用空格阁开，在它们的后面输出最大的乘积m，格式为max=m。

输入样例：
-5
10
1001

输出样例：
invalid input!
2 3 5 max=30
invalid input!

我的算法思想是
1）.把一个正整数从中间分开（如果是偶数，直接除以2；如果是奇数，分别加1除以2，减1除以2）
2）.其中一部分保留在mem[]数组中（奇数的话，比较大的那一部分保留给mem[]数组），另一部分赋给temp，并重复1，2 步骤
3）.最后把temp赋给mem[]数组

代码： 全选

//11.cpp
#include<iostream>
using namespace std;

int main()
{
	const int N=50;
	int mem[N];
	int n;
	while(cin>>n)
	{
		int temp=n;
		int num=0;
		if(n<=0||n>50)
			cout<<"invalid input!"<<endl;
		else
		{
			while(temp!=1&&temp!=2&&temp!=3&&temp!=4)
			{
				if(temp%2==0)
				{
					mem[num++]=temp/2;
					temp=temp/2;
				}
				else
				{
					mem[num++]=(temp+1)/2;
					temp=(temp-1)/2;
				}
			}
			mem[num]=temp;
			if(mem[num]==mem[num-1])   //由于要求为不同的自然数，所以有了这一步
			{
				mem[num]--;
				mem[num-1]++;
			}
			int max=1;
			for(int i=0;i<=num;i++)
				max*=mem[i];
			for(int i=num;i>=0;i--)
				cout<<mem[i]<<" ";
			cout<<"max="<<max<<endl;
		}
	}
	return 0;
}

[rob2468]

不知道我的这个算法对不对，谢谢大家给点意见

[cmdblock]

好像有点错误：
[cmdblock@wg tmp]$ ./a.out
12
2 4 6 max=48
12的最大值应该是6 6
分解成 3 3 3 3 答案该是81

[Jayi]

http://blog.csdn.net/Rappy/archive/2007 ... 03184.aspx
参考一下吧

[billbear]

当然是错的 不用看你的代码 数学上就不对

[BigSnake.NET]

好像有点错误：
[cmdblock@wg tmp]$ ./a.out
12
2 4 6 max=48
12的最大值应该是6 6
分解成 3 3 3 3 答案该是81

互不相同

这题可以用动态规划

[rob2468]

好像有点错误：
[cmdblock@wg tmp]$ ./a.out
12
2 4 6 max=48
12的最大值应该是6 6
分解成 3 3 3 3 答案该是81

正如ls说的，题目要求各不相同

[rob2468]

有没有谁能提供一些想法

[cmdblock]

给你提供个思路吧
你要把数分解到最后都是2和3组成，就可以了。

[BigSnake.NET]

给你提供个思路吧
你要把数分解到最后都是2和3组成，就可以了。

都说了，互不相同 ...

[cmdblock]

也就是可以用上面所说的动态规划算法

[billbear]

12 为例，3 4 5 显然比 2 4 6 强。“直接除以2” 是你未经证明的奇怪想法。你至少拿个小的数验证一下啊。

[cmdblock]

如果是互不相同的话，我给你个思路你试一试。
首先还是分解成所有的2和3
然后一个一个加，也就是说从2.，3，4，5,6，7...这样一个一个找

[billbear]

数学上，简单地累加 2+3+4+5+...+k 直到和首次超过或等于 n。
若等于n，就是答案
若超过，记和为S，则在 2,3,4,...k 的序列中去掉数 S-n 即可。
若 S-n=1，则去掉 2，k 变成 k+1

[rob2468]

数学上，简单地累加 2+3+4+5+...+k 直到和首次超过或等于 n。
若等于n，就是答案
若超过，记和为S，则在 2,3,4,...k 的序列中去掉数 S-n 即可。
若 S-n=1，则去掉 2，k 变成 k+1

那我按ls这种算法还是提交不对，还是我哪里写错了，麻烦大家指点

代码： 全选

//11.cpp
#include<iostream>
using namespace std;
int main()
{
	int n;
	const int N=50;
	int ch[N];
	while(cin>>n)
	{
		int su=2;          //这个变量从2开始，后面不断自加，它是用来让temp不断的加的，相当于ls说的k
		int temp=0;     //这个就是ls所说的和S
		int result=1;
		if(n<=0||n>=50)
			cout<<"invalid input!"<<endl;
		else
		{
			while(temp<n)
			{
				temp+=su;
				su++;
			}
			if(temp==n)            //case 1
			{
				for(int i=2;i<su;i++)
				{
					cout<<i<<" ";
					result*=i;
				}
				cout<<result<<endl;
			}
			else if(temp-n==1)       //case 2
				{
					for(int i=3;i<su;i++)
					{
						ch[i-3]=i;
						result*=i;
					}
					ch[su-4]=su;
					result=result/(su-1)*su;
					for(int i=3;i<su;i++)
						cout<<ch[i-3]<<" ";
					cout<<result<<endl;
				}
				else                  //case 3
				{
					int a=0;
					int b=temp-n;
					for(int i=2;i<su;i++)
					{
						if(i==b)
							continue;
						else
						{
							cout<<i<<" ";
							result*=i;
						}
					}
					cout<<result<<endl;
				}
		}
	}
	return 0;
}