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

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

算法实现题 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

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