问题描述:
有n美元需找零.
美元中有x美分,y美分,z美分,a美分,s美分
总共有多少种方式?
分成两步:
1.计算使用x美分找零的方法数.
2.上面数目加上除了使用x美分找零的方法数以外的数目.
演示@google code
代码:
想模仿 scheme 很棘手
/*
递归解法,金币找零问题,模仿 scheme
a:[{
value : value ,//当前零钱金额
index: index //当前标签
}]
*/
function countchange(a, limitW) {
var option=[];
var result=[];
function selectcount(i,value) {
option[i]=value;
return i;
}
function unselectcount(i) {
option[i]--;
}
function count_iter(i,remain) {
if(remain == 0) {
var tmp=[];
for(var j=0;j<option.length;j++){
if(option[j]) {
tmp.push("金额 "+ a[j].value+ " : "+option[j]+" 个 , ");
}
}
result.push(tmp);
return i;
}
if(remain>=a[i].value) {
//选择 a[i],计算,然后复原
unselectcount(
count_iter(
selectcount(i,(option[i]||0)+1),remain-a[i].value
)
);
}
//不选 a[i]
if(i<a.length-1)
count_iter(i+1,remain);
return i;
}
count_iter(0,limitW);
return result;
}
分享到:
相关推荐
C++贪心算法超市找零问题代码实现,分享给大家参考一下。
python数据结构与算法分析,动态规划—找零问题.py
详细的背包问题和超市找零问题的解说, 代码详细,注释清除,方便使用
下面是一个使用C语言实现的贪心算法示例,即“钱币找零问题”,目标是用最少的钱币数量来找零。 **题目:**给定不同面额的钱币和一个总金额,使用贪心算法计算出最少需要多少个钱币来凑出这个总金额。 要求: ...
下面是一个使用C语言实现的贪心算法示例,即“钱币找零问题”,目标是用最少的钱币数量来找零。 **题目:**给定不同面额的钱币和一个总金额,使用贪心算法计算出最少需要多少个钱币来凑出这个总金额。 要求: 1、...
下面是一个使用C语言实现的贪心算法示例,即“钱币找零问题”,目标是用最少的钱币数量来找零。 **题目:**给定不同面额的钱币和一个总金额,使用贪心算法计算出最少需要多少个钱币来凑出这个总金额。 要求: 1、...
01背包问题动态规划,动态规划求解找零问题和背包问题C++代码
主要介绍了java动态规划算法——硬币找零问题,结合实例形式分析了java动态规划算法——硬币找零问题相关原理、实现方法与操作注意事项,需要的朋友可以参考下
主要介绍了Python基于回溯法子集树模板解决找零问题,简单描述了找零问题并结合具体实例形式分析了Python使用回溯法子集树模板解决找零问题的步骤、实现方法与相关操作技巧,需要的朋友可以参考下
c语言实现找零问题的毕业设计、课程设计
题目找零问题, 给个金额让你找出对应的最小硬币数目背包问题解法?
C/C++实现贪心算法 钱币找零问题,假设有i种纸币,Values[i]元的纸币有Counts[i]张。现在要用这些钱来支付Total元,至少要用多少张纸币?
Scratch少儿编程项目源代码文件案例蓝桥训练-找零问题.zip
一场激烈足球赛即将开始,售票员紧张地卖票着……。 每张球票50元,现在有2n(1)个球迷排队购票,其中n个...假设开始售票时售票处没有零钱可以找零。 问这2n个人有多少种排队方式,不至使售票处出现找不出零的局面?
一个简单的动态规划算法实例,实现硬币找零的最小硬币数以及每种面额硬币的数量。
主要介绍了js贪心算法 钱币找零问题代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
主要介绍了Java动态规划之硬币找零问题实现代码,具有一定参考价值,需要的朋友可以了解下。
本文实例讲述了JS使用贪心算法解决找零问题。分享给大家供大家参考,具体如下: 前面介绍了JS贪心算法解决背包问题,这里再来看看找零问题的解决方法。 在现实生活中,经常遇到找零问题,假设有数目不限的面值为20,...
11085 买票找零 时间限制:1000MS 内存限制:65535K 提交次数:0 通过次数:0 题型: 编程题 语言: 无限制 Description 一场激烈足球赛即将开始,售票员紧张地卖票着……。 每张球票50元,现在有2n(1)个球迷排队...