问题描述:给定一组数额不等的硬币(数量不限),给定要找的数额,找出硬币数最少的解决方案(不考虑极端情况,最小硬币大于需要找零的数额);
分析:这是一个最简单的动态规划问题,采用贪心算法,每次尝试用最大数额的硬币,如果不行,回退到上一步,具体到代码是采用递归的方式来解决。
难点:
1.什么情况下无法找零
2.什么情况下需要回退,如何回退
3.什么情况需要继续采用贪心策略
在解决上面几个难点之前,需要对我们的贪心策略的规律有一些了解:
1.后排的硬币,不应该大于前排;
我们定义一个变量total,用来表示未找零的数额;定义min表示最小硬币的数额;
那么对于难点1,应该是第一个硬币是最小值,并且剩余未找零数额不为0且小于最小值时;
对于难点2,当total小于min并且队伍里面存在大于min的硬币,那么我们可以将硬币替换成其它硬币来尝试新的检索;
对于难点2,回退策略应该是:从队列末尾找出一个比min大的硬币,用比这枚硬币稍小的硬币替换,并将后续的节点全部清除;
对于难点3:只要total大于min,我们就可以选择硬币中尽量大的并且不大于队列末尾值的硬币来填充。
下面是java代码:
package dp;
import java.util.LinkedList;
import java.util.List;
/**
* 硬币找零
*/
public class GetChange {
private static int[] coins = {1, 3, 4, 5};
public static void main(String args[]) {
List<Integer> list = new LinkedList<>();
circle(list, 2);
System.out.println(list);
}
private static void circle(List<Integer> list, int total) {
//找零完成
if (total == 0)
return;
//找零失败
if (list.get(0) == coins[0] && total < coins[0])
return;
//回退操作
if (total < coins[0]) {
for (int i = list.size() - 1; i >= 0; i--) {
//从队伍末尾开始,找到第一个可以变小硬币
boolean flag = false;
for (int j = coins.length - 1; j >= 1; j--) {
if (coins[j] == list.get(i)) {
//找到了
flag = true;
//清除后面的硬币
for (int k = list.size() - 1; k >= i; k--) {
total = total + list.get(k);
list.remove(k);
}
list.add(coins[j - 1]);
total = total - coins[j - 1];
break;
}
}
if (flag) {
//退出外层循环
break;
}
}
circle(list, total);
return;
} else {
//贪心策略
for (int i = coins.length - 1; i >= 0; i--) {
//加入条件,硬币尽可能大,并且不大于队伍尾数
if (list.size() > 0) {
if (coins[i] <= total && coins[i] <= list.get(list.size() - 1)) {
list.add(coins[i]);
total = total - coins[i];
break;
}
} else {
if (coins[i] <= total) {
list.add(coins[i]);
total = total - coins[i];
break;
}
}
}
circle(list, total);
return;
}
}
}
分享到:
相关推荐
一个简单的动态规划算法实例,实现硬币找零的最小硬币数以及每种面额硬币的数量。
算法设计 硬币找零 程序 算法设计 硬币找零 程序 算法设计 硬币找零 程序 算法设计 硬币找零 程序
这是一个利用动态规划的最少硬币找零算法,时间效率符合要求
主 要 用 于 M K 2 硬 币 器 开 发,及 测 试 程 序!
中文版,富士硬币找零器MDB通信协议,协议非常详细,1.适用范围 本规格适用于采用MDB通信的硬币兑换器,对主控部分与硬币兑换器之间的串联信号传送方式作出规定。 2.基本通信规格 2.1 概要 依照MDB/...
Hopper硬币机、硬币找零机对接开发资料。编程基本流程说明,通信协议说明。
主要介绍了java动态规划算法——硬币找零问题,结合实例形式分析了java动态规划算法——硬币找零问题相关原理、实现方法与操作注意事项,需要的朋友可以参考下
主要介绍了Java动态规划之硬币找零问题实现代码,具有一定参考价值,需要的朋友可以了解下。
bccs:Bcube硬币找零解决方案
贪心算法 找零钱 c语言 简洁 绝对无误
找零是寻找使用给定面额集可以达到目标数量的方式的问题。
尽管贪心算法可能不总能得到绝对最优解,但在硬币找零问题中,它能提供一个有效的近似解。这种方法已被证明在硬币面值组合为特定集的情况下是最优的,如美国货币系统。贪心算法的实现在不同编程语言中逻辑一致,但...
" " "纸币收款 " " "硬币收款 " " "硬币找零 " " "非接充值卡收款 " " "支付宝、财付通等收款 " " "微信支付收款 " "开放云平台 "电子商务平台及后台管理功能 " "业务前端 "微信开发 " " "Android APP开发 " " "苹果...
硬币组合 一个 JavaScript 网络应用程序,它返回与用户输入的美分值匹配所需的最少数量的美元硬币(即四分之一、一角硬币、镍币、便士)。 在 、 和的帮助下编写。 用法 在浏览器中,打开titleCase.html文件。 关于 ...
凑硬币 LeetCode_No.322_-零钱兑换 题目介绍 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。 你可以...
1.Knapsack Problem 2.最优装载 3.程序存储问题 4.Maximum Tape Utilization Ratio 5.汽车加油问题 6.活动安排问题 7.硬币找零 8.整数连接 . .
:针对售卖袋装、盒装、软瓶装小商品的自动售货机设计...系统以16位单片机sPcE061A为控制核心,可实现货币识别、商品选择、硬币找零、商品输出、金额显示、语音提示等功能.具有 智能化的人机界面,功能强、使用方便.
算法问题解决 用于准备编程比赛的算法和数据结构(例如ACM-ICPC,)和编码...动态编程一些硬币找零的例子: from tryalgo import coin_change print ( coin_change ([ 3 , 5 , 11 ], 29 )) # True because 29 = 6 x 3
231测试CATCHER 260 Il Gioco dell'X 299火车交换 315网络 第336章太过分了 383条运输路线 473喧闹的摇杆 482个排列阵列 514护栏 558虫洞 562个分币 612 DNA分选 673括号内的余额 674硬币找零 821跳页 908重新连接...