求解下面的程序是哪写错了吗？

Question

var cnt = 0;

function change(target, coins, usable) {

    coin = coins.shift();

    if(coins.length==0) {

        if(target/coin<=usable) {

            cnt += 1;

        }

    }

    else{

        for(let i=0; i<=target/coin; i++) {

            change(target-coin*i, coins, usable-i);

        }

    }

}

change(1000, [500, 100, 50, 10], 15);

console.log(cnt);

算法题目链接：https://max.book118.com/html/...。

题目：当下，坐公交或者地铁时大部分人都是刷卡的。不过，时至今日还在用现金支付的人还是比想象的多。本题我们以安置在公交上的零钱兑换机为背景。

这个机器可以用纸币兑换到 10 日元、50 日元、100 日元和 500 日元硬币的组合，且每种硬币的数量都足够多（因为公交接受的最小额度为 10 日元，所以不提供 1 日元和 5 日元的硬币）。

兑换时，允许机器兑换出本次支付时用不到的硬币。此外，因为在乘坐公交时，如果兑换出了大量的零钱会比较不便，所以只允许机器最多兑换出 15 枚硬币。譬如用 1000 日元纸币兑换时，就不能兑换出“100 枚 10 日元硬币”的组合。

求兑换 1000 日元纸币时会出现多少种组合？注意，不计硬币兑出的先后顺序。

Answer 1

var cnt = 0;function change(target, coins, usable) {&nbsp; &nbsp; let coin = coins.shift();//应该要给coin声明变量,不声明会默认全局变量则导致下面for循环的值跟着变动,就一直不满足target/coin<=usable的条件.&nbsp; &nbsp; if(coins.length==0) {&nbsp; &nbsp; &nbsp; &nbsp; if(target/coin<=usable) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; cnt += 1;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; else{&nbsp; &nbsp; &nbsp; &nbsp; for(let i=0; i<=target/coin; i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; change(target-coin*i, coins.slice(), usable-i);//这里应该复制一份coins,避免递归时候使用shift把数据给修改了.&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }}change(1000, [500, 100, 50, 10], 15);console.log(cnt);

Answer 2

coins.shift() usable不知道你些内容是怎么定义的？

Answer 3

既然是算法题，就应该先考虑算法其实这个问题转化后就是求 有4个不同的数字在数组A中，抽取每个数字（允许多次抽取）总抽取数位N（N<=15），使得其总和等于X,问有多少可能（最少可能是0个，即不能匹配抽取）当然，因为这个题中X和A已经确定了，所以可以减少搜索规模。前面给出了一种方法，我想用另外一种方法求解（位运算）根据前面的一些条件，其实可能可以映射到一个2bit（最大值为3）+4bit（最大值为15）+4bit（最大值为15）+4bit（最大值为15） 是数字上其中2bit对应于500的数量，因为刚好等于2的可能是唯一的，所以可以退化为1bit+4bit+4bit+4bit的数字上(一共13bit)且各段数据总和小于等于15,第二段也要小于等于10，所以遍历符合条件的数字，就可以获取最终结果了。下面是实现（这个题对这个来说不是最优解，但如果A数据量扩大，N扩大和X扩大，则可能是较优解，因为只是单纯的遍历了，是O(N)复杂度算法），且这个算法实现逻辑也比较简单，语句也比较简单。var A=[500,100,50,10];//var RT=[[2,0,0,0]];//存储最终结果var s=0x1AFF; //起始数据for(;s>0;s--){&nbsp; &nbsp; //提取各个的系数&nbsp; &nbsp; a0=s>>12;&nbsp; &nbsp; a1=(s>>8)&0xf;&nbsp; &nbsp; a2=(s>>4)&0xf;&nbsp; &nbsp; a3=s&0xf;&nbsp; &nbsp; if(a1>10 || a0+a1+a2+a3>15) continue; // 过滤掉不符合系数条件的&nbsp; &nbsp; if(a0*A[0]+a1*A[1]+a2*A[2]+a3*A[3] ===1000) RT.push([a0,a1,a2,a3]);}console.log(RT);var cnt=RT.length;console.log(cnt);//输出可能数量