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

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) {

    let coin = coins.shift();//应该要给coin声明变量,不声明会默认全局变量则导致下面for循环的值跟着变动,就一直不满足target/coin<=usable的条件.

    if(coins.length==0) {

        if(target/coin<=usable) {

            cnt += 1;

        }

    }

    else{

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

            change(target-coin*i, coins.slice(), usable-i);//这里应该复制一份coins,避免递归时候使用shift把数据给修改了.

        }

    }

}

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--){

    //提取各个的系数

    a0=s>>12;

    a1=(s>>8)&0xf;

    a2=(s>>4)&0xf;

    a3=s&0xf;

    if(a1>10 || a0+a1+a2+a3>15) continue; // 过滤掉不符合系数条件的

    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);//输出可能数量