Java实现币值最大化问题
JAVA 实现 最大化 问题
2023-09-14 08:58:13 时间
1 问题描述
给定一排n个硬币,其面值均为正整数c1,c2,…,cn,这些整数并不一定两两不同。请问如何选择硬币,使得在其原始位置互不相邻的条件下,所选硬币的总金额最大。
2 解决方案
2.1 动态规划法
本文所写代码思想参考自《算法设计与分析基础》第三版上一段讲解,具体如下:
package com.liuzhen.chapter8;
import java.util.ArrayList;
public class CoinRow {
/*
* 参数Money:给定硬币组合面值数
* 函数功能:以数组链表形式返回最大总金额硬币组合的数组下标以及最大总金额,
* 其中链表中最后一个元素为最大总金额,其它元素为硬币组合数组下标
*/
public ArrayList<Integer> getMaxSumCoin(int[] Money){
ArrayList<Integer> list = new ArrayList<Integer>();
if(Money.length == 1){ //当给定硬币个数只有一个时,最大总金额即为该枚硬币
list.add(0); //存放硬币位置
list.add(Money[0]); //存放硬币总金额
return list;
}
int[] tempMaxSum = new int[Money.length]; //用于存放遍历到当前硬币位置(从前到后遍历)的最大总金额
tempMaxSum[0] = Money[0];
if(Money[0] < Money[1])
tempMaxSum[1] = Money[1];
else
tempMaxSum[1] = Money[0];
for(int i = 2;i < Money.length;i++){
if(tempMaxSum[i-1] >= tempMaxSum[i-2] + Money[i])
tempMaxSum[i] = tempMaxSum[i-1];
else
tempMaxSum[i] = tempMaxSum[i-2] + Money[i];
}
System.out.println("\n当前位置硬币的最大金额:");
for(int i = 0;i < Money.length;i++)
System.out.print(tempMaxSum[i]+" ");
//根据tempMaxSum数组元素,找出,最大金额的硬币组合元素的数组下标
for(int i = Money.length-2;i >=0;i--){
int temp = tempMaxSum[i];
if(temp < tempMaxSum[i+1]){
list.add(i+1); //存放最大金额硬币组合元素数组下标
temp = tempMaxSum[i+1] - Money[i+1];
for(int j = 0;j < Money.length;j++){ //寻找到tempMaxSum数组(从小到大排序)中第一个等于temp值的元素
if(tempMaxSum[j] == temp){
i = j;
break;
}
}
}
}
if(Money[0] >= Money[1]) //不管怎样选择硬币组合,在前两枚硬币中一定会选一枚
list.add(0);
else
list.add(1);
list.add(tempMaxSum[Money.length-1]); //存放硬币最大总金额
return list;
}
public static void main(String[] args){
CoinRow test = new CoinRow();
int[] Money = {1,1,2,10,6,2,10,8,12};
System.out.println("当前位置硬币的金额:");
for(int i = 0;i < Money.length;i++)
System.out.print(Money[i]+" ");
ArrayList<Integer> list = test.getMaxSumCoin(Money);
System.out.println("\n最大总金额硬币组合的数组下标依次为:");
for(int i = 0;i < list.size()-1;i++)
System.out.print(list.get(i)+" ");
System.out.println("\n最大总金额硬币组合的对象数组下标相应面值依次为:");
for(int i = 0;i < list.size()-1;i++)
System.out.print(Money[list.get(i)]+" ");
System.out.println("\n"+"最大总金额为:");
System.out.println(list.get(list.size()-1));
}
}
运行结果:
当前位置硬币的金额:
1 2 10 6 2 10 8 12
当前位置硬币的最大金额:
1 3 11 11 13 21 21 33
最大总金额硬币组合的数组下标依次为:
6 3 0
最大总金额硬币组合的对象数组下标相应面值依次为:
10 10 1
最大总金额为:
相关文章
- 【Java】java扩展机制SPI 实现
- Java实现 蓝桥杯 算法训练 Beaver's Calculator
- Java实现 蓝桥杯 算法训练 相邻数对(暴力)
- Java实现 LeetCode 677 键值映射(字典树)
- Java实现 LeetCode 638 大礼包(阅读理解题,DFS)
- Java实现 LeetCode 481 神奇字符串
- Java实现 LeetCode 405 数字转换为十六进制数
- java实现多线程(车站卖票)
- java实现数组转置
- Java实现第九届蓝桥杯复数幂
- Java实现币值最大化问题
- Java实现 蓝桥杯VIP 算法提高 3-2求存款
- Java实现 蓝桥杯VIP 算法训练 星际交流
- Java 蓝桥杯 算法训练 字符串的展开 (JAVA语言实现)
- Java 蓝桥杯 算法训练 字符串的展开 (JAVA语言实现)
- Java 蓝桥杯 算法训练 字符串的展开 (JAVA语言实现)
- Java实现批量修改文件名称
- 使用Java标准的java.util.EventListener实现观察者-发布者设计模式
- 40个问题让你快速掌握Java多线程的精髓
- java-信息安全(十二)-数字证书、CA证书【Java证书体系实现】
- JAVA语言之Java 中不同的并行实现的性能比较
- 【java基础】输入/输出流基本介绍