Java教程

【贪心算法】最优分解问题

本文主要是介绍【贪心算法】最优分解问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

算法实现题 4-15 最优分解问题

问题描述:

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

算法设计:

对于给定的正整数 n,编程计算最优分解方案。

数据输入:第 1 行是正整数 n。

结果输出:将计算的最大乘积输出到屏幕。

input:10

output:30

来自以下博文:https://blog.csdn.net/qq_38360701/article/details/80387719

  问题分析: 整数的一个性质:若 a + b =N(常数),则| a - b |越小, a * b 越大    

 证明 :当 n < 4 时, n 的分解的乘积小于 n ;
           当 n >= 4 时,n = 1 + ( n – 1 ) 因子的乘积也是小于 n ;
           所以 n = a + ( n – a ),2 ≤ a ≤ n - 2,可以保证乘积大于 n,即越分解乘积越大。
 

贪心策略:将n分成从2开始的连续自然数的和,如果最后剩下一个数,将此数在后项优先的方式下均匀地分给前面各项。

该贪心策略首先保证了正整数所分解出的因子之差绝对值最小,即|a - b|最小;同时又可以将其分解成尽可能多的因子,且因子的值较大,确保最终所分解的自然数的乘积值。

当n小于4的时候,就会出现矛盾,,,,,,

比如n=4,最小从2开始,剩余2,不够3,这个时候就要均分给前面的数字每人一个1,可是前面只有1个数字,全加给那一个数吧,又相当于没有分解,要是不从2开始,从1开始分解,对于其他大数又不合理,,,要单独考虑,这个程序可能把那个剩下的1分给了越界的数组下标,还要保证题目上的互不相同的要求,只能理解成分为1+3,乘积最大是3。。。

#include<bits/stdc++.h>
using namespace std;

int main() {
	int n;
	cin>>n;
	int x=n;
	int i=2,j=0,a[99999];
	while(x>=i) {
		a[j++]=i;
		x=x-i;
		i++;
	}
	int p=j-1;
	while(x--) {
		a[p--]++;
	}
	int sum=1;
	for(int s=0; s<j; s++) {
		sum=sum*a[s];
	}
	cout<<sum<<endl;
//	for(int s=0; s<j; s++)
//		cout<<a[s]<<" ";
	return 0;
}

 

以下来自这位博主的图片。

https://blog.csdn.net/weixin_43787043/article/details/105784494

这篇关于【贪心算法】最优分解问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!