最优分解问题贪心求解

问题描述

设m是一个正整数，现在要求将n分解为若干个互不相同的自然数的和，且使得这些自然数的乘积最大。 注意：这个问题不同于剪绳子问题，因为剪绳子问题可以使得每一段重复相等，而此问题必须使得划分出来的每一个数都互斥。

算法设计

对于给定的正整数m，要求计算最优分解方案

数据输入

输入只有1行，表示整数m

输入样例1：

10

输入样例2：

100

数据输出

输出有两行 第一行表示整数m划分的各个自然数，每个数之间有一个空格，划分的数按照升序排列。 第二行表示这个最大的乘积。 输出样例1：

2 3 5 30

输出样例2：

2 3 5 6 7 8 9 10 11 12 13 14 21794572800

思路

贪心算法。如果a+b=n，则|a-b|越小，那么ab越大，如老师所讲，可以将n分解成从2开始的连续自然数的和。 例如：输入n=10，则可以分解为 2、3、4，还剩下1不够5，把这个1倒着加，4 -> 5。 所以，最终分解为2,3,5，结果为23*5=30。

证明见贪心算法-最优分解

代码

#include <iostream> #include<stdio.h> #include<string.h> using namespace std; int a[101];//用来存入划分的每个数 /* 贪心算法。如果a+b=n，则|a-b|越小，那么a*b越大，如老师所讲，可以将n分解成从2开始的连续自然数的和。 例如：输入n=10，则可以分解为 2、3、4，还剩下1不够5，把这个1倒着加，4 -> 5。 所以，最终分解为2,3,5，结果为2*3*5=30。 */ int main() { int m; cin>>m;//输入待划分的整数 a[1]=2;//使得互斥和乘积最大，a[1]=2, m=m-2; int i; //往后的数依次递增直到不满足条件为止 for(i=1;m>=a[i]+1;i++){ a[i+1]=a[i]+1; m=m-a[i+1]; } int n=i;//一共有n个数 //将剩余的不能划分成的数m依次从后往前分配给每一个数，一次分配一个1 //从后往前均匀分配 while(m!=0){ a[i]++;//对a[i]分配一个1 m--;//剩下未分完的数减去1 //一共有n个数，标号为1-n，步长为n //每次向前偏移距离1，offset=-1 //初始标号start=1，末尾标号end=n //i=(i-start+offset)%n+start; i=(i-1-1+n)%n+1;//i在(1-n)中循环向前移动一个距离 } //p用来存放最大乘积 long long p=1; //输出最后划分出来的n个数 for(int i=1;i<=n;i++){ cout<<a[i]<<" "; p=p*a[i]; } cout<<endl<<p;//输出最大乘积 }