一、找硬币的问题
1.找最少的硬币
2.有多少种求解的方式
二、分析求解
我看有些说用动态规划树来求解?
可是我现在对动态规划树的理解停留在背包问题上,也就是个数是定的,然后求的价值
找硬币的话硬币个数不定?怎样转化?
1.直接求解最少的硬币 直接存放结果
//当前存放的值,是上一个面值额的数多放一个硬币比较结果 //每次都有每个硬币的一个选择 //但是最多是最小硬币的那个个数 //求的最小的值然后替换 //所以面值要先排序得到最小面值这里没接默认为1 public static void test(int[]coins,int[] vesult,int money){ for(int i=1;i<=money;i++){ int min=i; for(int j=1;j<coins.length;j++){ if(coins[j]<=i){ int temp=vesult[i-coins[j]]+1; if(temp<min)min=temp; } } vesult[i]=min; System.out.println(i+"需要组合个数:"+min); } }
2.动态求结果
//每次保存的是选择的有效最小个数,所谓的背包价值,个数不定,所以要循环 //求的结果的时候可能不是唯一的但是没次最大有结肯定是最少的 //初识化的时候默认为1的时候所以默认值是最小面值的那个个数 public static void getCoinMethod(int[]coins,int[][]result,int money){ //result是一个二维的数组 // x标示coin的种类,y标示的结果的大小 for(int init=1;init<=money;init++){ result[1][init]=init; } for(int i=2;i<coins.length;i++){ for(int j=1;j<=money;j++){ result[i][j]=result[i-1][j]; int count=j/coins[i]; for(int k=0;k<=count;k++){ if(result[i][j]>result[i-1][j-k*coins[i]]+k) result[i][j]=result[i-1][j-k*coins[i]]+k; } } //System.out.println(Arrays.toString(result[i])); } System.out.println(money+"组合数:"); for(int n=coins.length-1;n>0;n--){ int count=money/coins[n]; if(money>=coins[n]&&result[n][money]==(result[n-1][money-coins[n]*count]+count)){ money=money-coins[n]*count; System.out.print(coins[n]+":"+count+"个 "); } } System.out.println(); }
相关推荐
是本人自己写的,也没有借鉴他人,用C语言写的
人工智能领域经典算法的例子。启发式函数搜索:十二硬币问题是采用AO*算法,野人过河采用A算法求解。内附有实例演示
贪心算法求解最少硬币问题C语言程序,问题描述:给顾客找零钱时,收银处有1元,5角和1角硬币若干,如何用最少数量的硬币找够零钱? 算法思想:比如要找给顾客2元9角钱,首先计算1元最多可以有多少枚,即2枚,减去2元,还...
你的任务是找出这个伪造的硬币。为了帮助你完成这一任务,将提供一台可用来比较两组硬币重量的仪器,利用这台仪器,可以知道两组硬币的重量是否相同。试用分治法的思想写出解决问题的算法,并计算其时间复杂度。 2....
在n枚外观相同的硬币中,有一枚是假币,并且已知假币与真币的重量不同,但不知道假币与真币相比较轻还是较重。可以通过一架天平来任意比较两组硬币,设计一个高效的算法来检测这枚假币。
减制法实现在N枚硬币中找出重量不一致的硬币.运行环境DEV c++通过测试 可以运行
对最少硬币兑换问题的算法进行了分析,并给出了实现
对于任意钱数,设计一个用最少硬币找钱的方法 数据输入:由文件input.txt提供输入数据,文件的第一行中只有一个整数给出n的值,第二行起每行2个数,分别是T[j]和cion[j].最后一行是要找的钱数m。 解题思路:可以...
有n枚硬币 从中找出一个硬币 效率较高的方法 类似于减治法
问题描述:在n枚外观相同的硬币中,有一枚是假币,并且已知假币较轻。通过一架来任意比较两组硬币,从而得知两组硬币的重量是否相同,或者哪一组更轻一些,假币问题要求设计一个高效的算法来检测出这枚假币。
某个国家仅有1分、2分、5分硬币,将钱n(n>=5)兑换成硬币有很 多种兑法,编写实验程序计算出10分钱有多少种兑法,并列出每种 兑换方式。 3.沙漠问题 题目描述: -辆吉普车来到1000km宽的沙漠边沿。吉普车的耗油量为1L ...
通过matlab编写程序,对经典的抛硬币实验进行仿真
算法设计与分析作业:动态规划———硬币问题源码
掌握分治法、贪心算法的概念和基本思想,并结合具体的问题学习如何用相应策略进行求解的方法,代码详细,可运行
设计算法求解最少硬币问题,并编程实现,超市找零钱时,找钱数最少的方法
设计一个求解该问题的算法,给出算法的伪码描述并分析算法的时间复杂度.假设问题的输入实例是:v1=1,v2=4,v3=6,v4=8w1=1,w2=2,w3=4,w4=6y=12给出算法在该实例上计算的备忘录表和标记函数表并说明付钱的方法。
EM算法,抛掷、投掷硬币问题,迭代求解E步、M步
就是N枚硬币,其中一枚是假币,假币和真币不知道重量,治可以用一个没有刻度的天平测,求出假币是哪一枚,用的是分治法
对于n=25找零方式可以分解为四个解空间,然后再对子空间进行分解,很容易用递归完成。 代码如下 class Solution: def __init__(self): self.num = 0 #总次数 def waysToChange(self, n: int) -> int: def ...
C 抛硬币获取正面的频率图算法,计算概率的,假设每次抛10次为一事件,记录每次得到正面的次数,共抛掷100000次,计算得到正面次数的概率发布,并绘图输出结果。 思路:数值概率算法常用于数值问题的求解,此类...