最优分解问题 贪心算法
2021/12/13 20:49:23
本文主要是介绍最优分解问题 贪心算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
最优分解问题
问题描述:
设n是一个正整数,要求将n分解为若干互不相同的自然数之和,且这些自然数的乘积最大。
输入:
正整数n
输出:
计算的最大乘积。
如输入10,则输出30.
提示:
若a+b的值为一个常量,则a-b的绝对值越小,ab值越大。贪心策略:将n分成从2开始的连续自然数之和,如果最后剩下一个数,则将此数在后项优先的方式下均匀地分给前面各项。
import java.util.Scanner; public class Optimal_decomposition_problem {//贪心算法 最优分解问题 public static void main(String args[]){ Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int []Max = new int[100];//假设最大数为5150 Max[0] = 2; int i = 0; while (true) { if(Max[i] > n){ int j = i - 1; while (n > 0) { Max[j]++; j--; n--; if(j < 0){ j = i - 1; } } break; } n -= Max[i]; Max[i + 1] = Max[i] + 1; i++; } int sum = 1; for(int m =0;m < i;m++){ sum *= Max[m]; } System.out.println(sum); } }
这篇关于最优分解问题 贪心算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现