最优分解问题(JAVA)

mac2024-03-21  28

设n是一个正整数,现在要求将n分解为若干个互不相同的自然数的和,使这些自然数的乘积最大。 输入 10 输出 30 (被分解为5 2 3)

分析:

一个数被分为任意2个为不为一的数都大于等于原数。那就可以根据这条性质去用贪心策略解决问题。

那从2开始,如果能分解出来就要  10-2=8    8-3 =5  5-4=1<4

到了5那里就是我们的判断条件,因为题目要求分解为不相同的自然数,如果被分解的数分出来以后比分解出来的数小,那么就停止分解,因为再分出来的数要么是重复的要么是1

算法实现:

public static int resoleMax(int num) { int i=2; int max =1; while(num-i>i){ max*=i; num-=i; i++; } return max*num; }

 

最新回复(0)