how to calculate the ways of a big number split by some small numbers in js

Question

For example: There is a total number 1000, and how many ways to equal 1000 using 100/50/20/10/5/1. I have found a idea about this. But obviously, that's not good. So does anyone have some other good ideas to cover it?

total = prompt('you can input number 1-1000, but 1000 will take a LOONG time');
count = 0;
t100 = total;

function money() {
  for (var i100 = Math.floor(t100 / 100); i100 >= 0; i100--) {
    var t50 = t100 - i100 * 100;
    for (var i50 = Math.floor(t50 / 50); i50 >= 0; i50--) {
      var t20 = t50 - i50 * 50;
      for (var i20 = Math.floor(t20 / 20); i20 >= 0; i20--) {
        var t10 = t20 - i20 * 20;
        for (var i10 = Math.floor(t10 / 10); i10 >= 0; i10--) {
          var t5 = t10 - i10 * 10;
          for (var i5 = Math.floor(t5 / 5); i5 >= 0; i5--) {
            var t1 = t5 - i5 * 5;
            count++;
            console.log(i100 + ' 100' + i50 + ' 50' + i20 + ' 20' + i10 + ' 10' + i5 + ' 5' + t1 + ' 1');
          }
        }
      }
    }
  }
  alert('The total number ' + total + ' is ' + count);
}

money()

Here is a duplicate for you: http://stackoverflow.com/questions/1106929/how-to-find-all-combinations-of-coins-when-given-some-dollar-value — dfsq, May 09 '17 at 11:32
I think it belongs at codereview and then it is likely a duplicate of https://codereview.stackexchange.com/questions/120642/getting-all-divisors-from-an-integer — mplungjan, May 09 '17 at 11:32
Woah! This is O(n^5) (right?). Commenting to follow up tomorrow unless someone beats me to it or it's dead. — klvs, May 09 '17 at 11:56
@Matt: recursive function is also my consideration. And I have already tried it, but failed =.=. — Echo Xiao, May 10 '17 at 12:58
@EchoXiao: I don't see what is wrong with your code. Can you provide failed test cases ? Even if you do a recursive function, the complexity will be the same since you are just explicitly doing the recursive algorithm. If you want to significantly improve your algorithm, I think you will have to go for mathematics considerations. — Matt, May 10 '17 at 14:14
@EchoXiao: I just tought, you could do it recursively storing intermediate results in an array to save a lot of time avoiding recomputing already called computation — Matt, May 10 '17 at 14:22
Something that can be written iteratively can be written recursively but one may be more suitable. I think your answer is correct and I may be wrong but you. @Matt I think you may be right in a way though the answer isn't just recursion. I think you're talking about memoizing values which, though I'm no expert, might start to touch on dynamic programming which is a pretty complex https://www.youtube.com/watch?v=e0CAbRVYAWg — klvs, May 10 '17 at 23:18
@klvs Yes that is exactly what I am talking about, I didn't know the proper term, thanks for the link. — Matt, May 11 '17 at 00:01

score 0 · Answer 1 · answered May 09 '17 at 11:39

0

No idea if it's correct but a little idea that popped to my head:

You know that with the bills/coins given, you can always fill up to the amount you need (value). If at the same time, you assume that you will always chose the highest possible bill / coin for the remainder I think you could do this:

If you use 100 bills you have floor(value / 100) possibilities (You can use 1 x 100, 2 x 100... )

If you don't use 100 but 50 you have floor(value / 50) possibilities

If you don't use 50 but 20 you have floor(value /20) possibilities

and so on. Add those up and you have a total of possibilities.

Let me know if I'm missing something.

answered May 09 '17 at 11:39

Christian Ziegler

111
6

Once you use for exemple one 100 bill, you still have many possibilities to change the remaining amount – Matt May 09 '17 at 11:43
Yes, that's what I meant by "you assume that you will always chose the highest possible bill". Say if you use 2 x 100 and you fill up the rest with 50 as much as you can and then 20 and so on, then it should be only one possibility right? – Christian Ziegler May 09 '17 at 11:53
Yes but with this assumption, you can only find one possibility, am I wrong ? Maybe I don't understand what you mean – Matt May 09 '17 at 12:16
I was thinking of a cash machine which ran out of 100, 50... bills. It will always try to fill up the rest with the highest possible bills I assume. But I missed something. Other bills can be low / empty as well. So yes you'd have to consider all the possibilities for the remainder as well. – Christian Ziegler May 09 '17 at 12:54
I really appreciate you guys trying your best to help me for this.But I don't think it means a cash machine which gives the change. It's more like "Given some dollar value like 1000, find all the combinations of coins that make up the dollar value. There are only 100, 50, 20, 10, 5, 1 (if they are possible)." PS: in js. – Echo Xiao May 10 '17 at 12:55

score 0 · Answer 2 · answered May 10 '17 at 14:57

I don't know about coding in js but you could try an algorithm like this one, which should be much more performant timely speaking. I'll try to make it as clear as possible :

availableCoins = [100, 50, 20, 10, 5] // all available coins exept 1
numberCoins = availableCoins.Length

mapResults = new Map[(int,int),int]

money(int total, int indexCoin){
  if ( indexCoin == numberCoins ) {
    return 1 // only coin 1 is available, there is only one solution
  }
  elseif ( mapResults.containsKey((total,indexCoin)) ) {
    return mapResults((total,indexCoin)) // if the result has already been computed
  }
  else {
    int count = 0
    int currentCoin = availableCoin[indexCoin]
    int upperbound = floor(total / currentCoin) // compute it before to avoid useless computation
    for (int i = 0; i <= upperbound; i++) {
      count += money(total - i * currentCoin, indexCoin + 1) // we assume only i of the current coin will be use
    }
    mapResults((total,indexCoin)) = count
    return count
  }
}

money(1000, 0)

Let me know if I have missed something or if it is not clear. I let you adapt it to js.

var miane = [100,50,20,10,5,1],count=0,edu1,edu2; function money(num,m){ edu1 = miane[m],edu2 = miane[m+1]; for(var i=Math.floor(num/edu1);i>=0;i--){ if(num-edu1*i>=0) { count++; if(num-edu1*i>0&&edu2){ money(num-edu1*i,m+1); }else { continue; } } } return count; } money(1000,0); I have tried the recursive function like this, but I failed. I will thank you a lot if you help me find out the problem. ^.^ — Echo Xiao, May 15 '17 at 12:17
@EchoXiao What do you mean by failed ? is it the wrong output or is there an exception ? Note that what you have implemented is not exactly what I have suggested — Matt, May 15 '17 at 12:26

score 0 · Answer 3 · answered Feb 02 '18 at 07:41

0

I have got a expression from my colleague, and here it is: //n is the total number

Change(n,m) {
    if(n===0) return 0;
    if(n<0 || m === 0) return 0;
    var dimes = [1, 5, 10, 20, 50, 100];
    return (change(n, m-1)+change(n-dimes[m-1], m));
}

answered Feb 02 '18 at 07:41

Echo Xiao

11

I excuted this and maybe we can fix it a little like this: var dimes = [1, 5, 10, 20, 50, 100]; function change(n,m){ if(n === 0) return 1; if(n<0 || m < 1) return 0; return (change(n, m-1)+change(n-dimes[m-1], m)); } console.log(change(1000,5)); – Echo Xiao Jun 25 '19 at 12:55

how to calculate the ways of a big number split by some small numbers in js

3 Answers3