js贪心算法 钱币找零问题代码实例

给定一组硬币的面额，以及要找零的钱数，计算出符合找零钱数的最少硬币数量。

例如，美国硬币面额有1、5、10、25这四种面额，如果要找36美分的零钱，则得出的最少硬币数应该是1个25美分、1个10美分和1个10美分共三个硬币。这个算法要解决的就是诸如此类的问题。我们来看看如何用动态规划的方式来解决。

对于每一种面额，我们都分别计算所需要的硬币数量。具体算法如下：

  1. 如果全部用1美分的硬币，一共需要36个硬币
  2. 如果用5美分的硬币，则需要7个5美分的硬币 + 1个1美分的硬币 = 8个硬币
  3. 如果用10美分的硬币，则需要3个10美分的硬币 + 1个5美分的硬币 + 1个1美分的硬币 = 5个硬币
  4. 如果用25美分的硬币，则需要1个25美分的硬币 + 1个10美分的硬币 + 1个1美分的硬币 = 3个硬币

示意图

方案4的硬币总数最少，因此为最优方案。

具体的代码实现如下：

function minCoinChange(coins, amount) {
  let result = null;
  if (!amount) return result;

  const makeChange = (index, value, min) => {
    let coin = coins[index];
    let newAmount = Math.floor(value / coin);
    if (newAmount) min[coin] = newAmount;
    if (value % coin !== 0) {
      makeChange(--index, value - coin * newAmount, min);
    }
  };

  const arr = [];
  for (let i = 0; i < coins.length; i++) {
    const cache = {};
    makeChange(i, amount, cache);
    arr.push(cache);
  }
  console.log(arr);
  let newMin = 0;
  arr.forEach(item => {
    let min = 0;
    for (let v in item) min += item[v];
    if (!newMin || min < newMin) {
      newMin = min;
      result = item;
    }
  });
  return result;
}

函数minCoinChange()接收一组硬币的面额，以及要找零的钱数。我们将上面例子中的值传入：

const result = minCoinChange2([1, 5, 10, 25], 36);
console.log(result);

得到如下结果：

[
 { '1': 36 },
 { '1': 1, '5': 7 },
 { '1': 1, '5': 1, '10': 3 },
 { '1': 1, '10': 1, '25': 1 }
]
{ '1': 1, '10': 1, '25': 1 }

上面的数组是我们在代码中打印出来的arr的值，用来展示四种不同面额的硬币作为找零硬币时，实际所需要的硬币种类和数量。最终，我们会计算arr数组中硬币总数最少的那个方案，作为minCoinChange()函数的输出。

当然在实际应用中，我们可以把硬币抽象成任何你需要的数字，这个算法能给出你满足结果的最小组合。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • JS基于贪心算法解决背包问题示例

    本文实例讲述了JS基于贪心算法解决背包问题.分享给大家供大家参考,具体如下: 贪心算法:在对问题求解时,总是做出在当前看来是最好的选择.也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解. 寻找最优解的过程,目的是得到当前最优解 部分背包问题:固定容积的背包能放入物品的总最大价值 物品 A B C D 价格 50 220 60 60 尺寸 5 20 10 12 比率 10 11 6 5 按比例降序尽可能多放入物品 function greedy(values, weight

  • JS中的算法与数据结构之列表(List)实例详解

    本文实例讲述了JS中的算法与数据结构之列表(List).分享给大家供大家参考,具体如下: 前言 前端很少有机会接触到算法,大多都交互性的操作,所以不少前端工程师会抱着这么一种想法:我是做前端的,为什么要学数据结构与算法?没有数据结构与算法,我一样很好的完成工作.实际上,算法是一个宽泛的概念,我们平时写的任何代码都可以成为算法,它是对一个问题的解决方案的准确而完整的描述,是解决一系列问题的清晰指令,它代表着用系统的方法描述解决问题的策略机制.随着现在互联网的飞速发展,前端工程师已不是靠几个选择器操

  • JS实现的RC4加密算法示例

    本文实例讲述了JS实现的RC4加密算法.分享给大家供大家参考,具体如下: RC4是一种简单的对称加密算法,在文本加密,通信加密等场景应用非常广泛. 在Web中可以用来对本地存储数据进行加密,比如存储cookie中的用户名和密码,敏感信息等. 以下是本人根据其思想基于JS实现的算法. //var ctext = rc4("我是明文","我是密码"); //var text = rc4(ctext, "我是密码"); function rc4(dat

  • JS使用贪心算法解决找零问题示例

    本文实例讲述了JS使用贪心算法解决找零问题.分享给大家供大家参考,具体如下: 前面介绍了JS贪心算法解决背包问题,这里再来看看找零问题的解决方法. 在现实生活中,经常遇到找零问题,假设有数目不限的面值为20,10,5,1的硬币. 给出需要找零数,求出找零方案,要求:使用数目最少的硬币. 对于此类问题,贪心算法采取的方式是找钱时,总是选取可供找钱的硬币的最大值.比如,需要找钱数为25时,找钱方式为20+5,而不是10+10+5. 贪心算法还是很常见的算法之一,这是由于它简单易行,构造贪心策略不是很

  • JS算法题之查找数字在数组中的索引位置

    前言 编写算法时,排序是一个非常重要的概念.它有各种各样的种类:冒泡排序.希尔排序.分块块排序,梳排序,鸡尾酒排序,侏儒排序 -- 这些可不是我瞎编的! 这个算法题能够让我们一睹精彩的世界.我们必须对数字数组进行升序排序,并找出给定数字在该数组中的位置. 算法说明 将值(第二个参数)插入到数组(第一个参数)中,并返回其在排序后的数组中的最低索引.返回的值应该是一个数字. 例如 getIndexToIns([1,2,3,4], 1.5) 应该返回 1,因为 1.5 大于 1(索引0),但小于 2(

  • nodejs中各种加密算法的实现详解

    nodejs中各种加密算法的实现详解

    前言 在大前端的趋势下,前端er也要懂点数据加密相关的知识才行,加密算法的实现和原理我们可以不用深究,毕竟加密是一门高深的学科,但是基本的加密方式和编码还是要掌握的,毕竟没吃过猪肉,猪跑还是见过的嘛. 我对常见的几种加密和签名的算法做个归纳,同时附上 nodejs 的编码实现. 加密算法 为了保证数据的安全性和防篡改,很多数据在传输中都进行了加密.举个场景的栗子,最近很多网站都升级到 https 协议, https 协议就是使用了非对称加密和hash签名,还有 github 使用的 ssh ,也

  • js贪心算法 钱币找零问题代码实例

    js贪心算法 钱币找零问题代码实例

    给定一组硬币的面额,以及要找零的钱数,计算出符合找零钱数的最少硬币数量. 例如,美国硬币面额有1.5.10.25这四种面额,如果要找36美分的零钱,则得出的最少硬币数应该是1个25美分.1个10美分和1个10美分共三个硬币.这个算法要解决的就是诸如此类的问题.我们来看看如何用动态规划的方式来解决. 对于每一种面额,我们都分别计算所需要的硬币数量.具体算法如下: 如果全部用1美分的硬币,一共需要36个硬币 如果用5美分的硬币,则需要7个5美分的硬币 + 1个1美分的硬币 = 8个硬币 如果用10美

  • java动态规划算法——硬币找零问题实例分析

    本文实例讲述了java动态规划算法--硬币找零问题.分享给大家供大家参考,具体如下: 问题描述 现在有3种硬币分别为:1元,5元,10元,现在给你63元,让你全部换成硬币,求出最小硬币数量,也就是说,怎么用最少的硬币数凑成63元. 分析问题 解决这个问题,我们可以将这个大问题分成若干个小问题,自下而上解决问题. 1元对应的最小硬币数是1 2元对应的最小硬币数是2 3元对应的最小硬币数是3 4元对应的最小硬币数是4 -- 63元对应的最小硬币数是XXX 假设我们将前边计算出的金额对应的最小硬币数像

  • js基本算法:冒泡排序,二分查找的简单实例

    知识扩充: 时间复杂度:算法的时间复杂度是一个函数,描述了算法的运行时间.时间复杂度越低,效率越高. 自我理解:一个算法,运行了几次时间复杂度就为多少,如运行了n次,则时间复杂度为O(n). 1.冒泡排序 解析:1.比较相邻的两个元素,如果前一个比后一个大,则交换位置. 2.第一轮的时候最后一个元素应该是最大的一个. 3.按照步骤一的方法进行相邻两个元素的比较,这个时候由于最后一个元素已经是最大的了,所以最后一个元素不用比较. function sort(elements){ for(var i

  • 原生js实现获取form表单数据代码实例

    本文实例为大家分享了原生js实现获取form表单数据的具体代码,供大家参考,具体内容如下 //获取指定form中的所有的<input>对象 function getElements(formId) { var form = document.getElementById(formId); var elements = new Array(); var tagElements = form.getElementsByTagName('input'); for (var j = 0; j <

  • js获取 gif 的帧数的代码实例

    使用 javascript 获取 GIF 图的帧数,如果帧数过大,则不让传到服务器 这里是使用一个插件: github地址为: https://github.com/buzzfeed/libgif-js <!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title></title> <meta name="viewport" con

  • js回溯法计算最佳旅行线路代码实例

    js回溯法计算最佳旅行线路代码实例

    回溯法 假如有 A,B,C,D四个城市,他们之间的距离用 G[V][E] 表示,为 无穷大,则表示两座城市不相通 现在从计算从某一个城市出发,把所有的城市不重复旅行一次,最短路径 其中G为: (Infinity表示城市不相通) var g = [ [Infinity,3 ,Infinity,8 ,9], [ 3 ,Infinity,3 ,10 ,5], [Infinity, 3 ,Infinity,4 ,3], [8 ,10 ,4 ,Infinity,20], [9 ,5 ,3 ,20 ,Inf

  • C++ 算法精讲之贪心算法

    C++ 算法精讲之贪心算法

    目录 选择排序 平衡字符串 买股票的最佳时机 跳跃游戏 钱币找零 多机调度问题 活动选择 无重叠区间 选择排序 我们熟知的选择排序,其采用的就是贪心策略. 它所采用的贪心策略即为每次从未排序的数据中选取最小值,并把最小值放在未排序数据的起始位置,直到未排序的数据为0,则结束排序. void swap(int* arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } void selectSort(int* a

  • c语言来实现贪心算法之装箱问题

    装箱问题,贪心算法求近似最优解 复制代码 代码如下: import java.util.Arrays; import java.util.Comparator; //装箱问题,贪心算法 public class Enchase {     public void test1() {         Integer[] boxs={34,6,40,2,23,12,12};         int boxCaptation=40;//箱子容量         //倒序         Arrays.

  • Java使用贪心算法解决电台覆盖问题(示例详解)

    java使用贪心算法解决电台覆盖问题 代码实现 /** * 贪心算法实现集合覆盖 */ public class Demo { public static void main(String[] args) { // 创建电台和地区集合 HashMap<String, HashSet<String>> broadcasts = new HashMap<>(); // 创建各个电台 HashSet<String> k1 = new HashSet<>

随机推荐