算法笔记_045:币值最大化问题(Java)
2024-09-15 02:07:50
目录
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 1 2 10 6 2 10 8 12
当前位置硬币的最大金额:
1 1 3 11 11 13 21 21 33
最大总金额硬币组合的数组下标依次为:
8 6 3 0
最大总金额硬币组合的对象数组下标相应面值依次为:
12 10 10 1
最大总金额为:
33
最新文章
- javascript 数字进制转换
- Java的常用对象①②
- C# 获取本机指定类型指定网卡的Ip地址
- 【转】Spring jar包详解
- 让background-color 无效
- 【转】IOS屏幕旋转与View的transform属性之间的关系,比较底层
- 如何用udev for asm in oracle linux 6
- WKWebview点击图片查看大图
- keil MDK编译器(V4.01)与H-JTAG的问题
- 关于c++中方法名前面的双冒号
- mysql事件机制——定时任务
- ActiveMQ学习系列(一)
- sqlplus: error while loading shared libraries: libsqlplus.so: cannot open shared object file
- 未能加载文件或程序集System.Web.Http.WebHost
- 注解之@PathVariable
- Django中的Templates
- 开通博客啦 Let‘s Go!
- SQL008存储过程总结
- Java Web之Servlet中response、request乱码问题解决
- 创建 StyledMapType 地图样式
热门文章
- 51nod1394 差和问题 值域线段树
- 快速傅里叶变换(FFT)相关内容汇总
- [BZOJ2594][WC2006]水管局长加强版(LCT+Kruskal)
- Educational Codeforces Round 43 (Rated for Div. 2) ABCDE
- DiskFileUpload上传与Spring的CommonsMultipartResolver上传对比
- DP练习 巡逻
- 洛谷P1462 通往奥格瑞玛的道路
- [转]Jquery实现页面定时跳转
- 探究react-native 源码的图片缓存
- 桥接模式:探索JDBC的接口