Greedy Algorithm in JavaScript

Question

Here is the question that I need to consult for help:

Write a greedy algorithm to make change with the fewest coins possible using the Greedy Algorithm. You are given an array of coin values and an amount: computeChange(coins, amount). Return an array with the counts of each coin.

For example: computeChange([50, 25, 10, 5, 1], 137) should return the array [2, 1, 1, 0, 2] which indicates how many of each coin: 2 50-cent pieces, 1 quarter (25 cents), 1 dime (10 cents), no nickels (5 cents), and 2 pennies (1 cent), which add up to 137 cents.

The array you return from computeChange should be the same length as the first argument (coins). Assume that coins contains the values of different coin types in decreasing order.

The greedy algorithm says that you repeatedly look for the largest coin less than or equal to the remaining amount of money, then subtract that coin from the remaining amount. When the remaining amount reaches zero (or less), return the counts of coins used. (This algorithm is not always optimal.)

You can change the variables COINS, which gives the values of the different coins you can use to make change, and AMOUNT, which is the total value of the change to make. Changing these values might be useful for debugging your program.

Here is my code which I did but it did not display the standard change for 36 cents. Can anyone help me? Thank you.

<html>
<head>
    <title>The Greedy Algorithm</title>

    <script>

// ======== Here is the problem to be solved:   ========
COINS = [50, 25, 10, 5, 1];
AMOUNT = 137
coincount = [0,0,0,0,0];

// ======== Here is where your solution begins: ========

// define the function named computeChange here:
function computeChange(coins, amount) {
  var i = 0; var creminder = AMOUNT; var ccoin; 

    while( i < COINS.length )
    {
      while ( COINS[i] <= creminder )
      {
        creminder = creminder - COINS[i];
        ccoin = coincount [i] ;
        ccoin += 1;
        coincount [i] = ccoin ;

      }

      i++;
    }

    return coincount;
}

// ===================================================================
// ======== Everything below here simply displays your output ========
// ======== Do NOT change anything below this line ===================
// ===================================================================


function rightJustify(s, w) {
    // return a string of width w with s in the rightmost characters and
    // at least one space on the left. For simplicity, assume w < 20.
    var slen = s.length;
    var blanks = "                    "
    return blanks.substr(0, Math.min(20, Math.max(1, w - slen))) + s;
}


function makeChange() {
    // compute change as an array: each element of change tells
    // how many of the corresponding value in COINS to give. The
    // total value should equal AMOUNT.
    var change = computeChange(COINS, AMOUNT);
    // now format the results. Output should look like:
    // NUMBER   VALUE
    //    1       50
    //    0       25
    //    1       10
    //    1        5
    //    3        1
    // TOTAL AMOUNT: 68 (total is correct)
    //
    // First, we'll do some type checking in case change is not of the
    // expected type.
    change = [].concat(change); // force whatever it is to be an array
    // it should be an array of numbers, so let's check
    for (i = 0; i < change.length; i++) {
        if (typeof(change[i]) != 'number') {
            return "Error: the function computeChange did not return " +
                   "an array of numbers.";
        }
    }
    if (change.length > COINS.length) {
        return "Error: the function computeChange returned an array " +
               "longer than the length (" + COINS.length + ") of COINS.";
    }
    if (change.length < COINS.length) {
        return "Error: the function computeChange returned an array " +
               "shorter than the length (" + COINS.length + ") of COINS.";
    }
    var output = "<pre>NUMBER   VALUE\n"
    var sum = 0;
    for (i = 0; i < change.length; i++) {
        sum += change[i] * COINS[i];
        var n = change[i].toString();
        var a = COINS[i].toString();
        output += rightJustify(n, 4) + rightJustify(a, 9) + "\n";
    }
    output += "TOTAL AMOUNT: " + sum + " (total is ";
    output += (sum == AMOUNT ? "correct" :
                               "incorrect, should be " + AMOUNT) + ")\n";
    return output;
}


function runSolution()
{
    parent.console.log('loaded, calling runSolution()\n');
    parent.console.log('answer: ' + document.getElementById('answer').toString());
    document.getElementById('answer').innerHTML = makeChange();
}

    </script>
</head>
<body>
    <!-- the output is displayed using HTML     -->
    <!-- the ? will be replaced with the answer -->
    <div id = "answer">?</div></p>
    <br>
    <script>runSolution();</script>
</body>
</html>

What do you mean it did not display the standard change for 36 cents. ? — fuyushimoya
– fuyushimoya, Commented Jun 27, 2015 at 16:30
What I meant was what is wrong with my codes or what i need to do to display the standard change for 36 cents coins? because I have been trying out and searching in the internet most of the examples are in VB and other programming languages but not in javascript. — user5040029
– user5040029, Commented Jun 27, 2015 at 16:34

fuyushimoya · Accepted Answer · 2015-06-27 17:49:46Z

4

Thoughts: After reading the replys, first at thought is that this may be used to other codes that we didn't see here, so we need to make the function sufficient to solve the question by input, not using the GLOBAL VALUES like AMOUNT, COINS and coincount, instead, use params given like coins and amount, and return a self created coincount.

I'll explain this directly use comments in the codes

function computeChange(coins, amount) {
    // Create a array that is used to return the final result, instead of the global one.
    var coincount = [];

    // use the given `amount` to set `creminder ` rather than `AMOUNT` which may not be accessible if your code is called otherplace rather than here.
    var i = 0; var creminder = amount; var ccoin;


    while( i < coins.length )
    { 
      // Lazily init the used coin for coin type i to 0.
      coincount[i] = 0;
      while ( coins[i] <= creminder )
      {
        creminder = creminder - coins[i];
        ccoin = coincount[i];
        ccoin += 1;
        coincount[i] = ccoin;
      }

      i++;
    }

    return coincount;
}

Your origin version's creminder is determined by AMOUNT, so no matter I call computeChanges(COINS, AMOUNT) or computeChanges(COINS, 37), the result will be the same, because the 37 in the second example is not used, ignored and creminder is still set to AMOUNT. Both Nina Scholz and I do is to make that given amount account, so it matters when your function generates a result set.

edited Jun 27, 2015 at 17:49

answered Jun 27, 2015 at 16:37

fuyushimoya

9,8133 gold badges30 silver badges34 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

fuyushimoya Over a year ago

Let us continue this discussion in chat.

Orelongz · Accepted Answer · 2018-08-26 05:01:17Z

1

While the answers above are very correct, I think one could also think of the solution to this particular problem in a different way.

With the example of computeChange([50, 25, 10, 5, 1], 137), a single loop could be used to get the required solution.

function computeChange(changeArray, amount) {
  const result = [];

  for (let i = 0; i < changeArray.length; i++) {
    let changeAmount = Math.floor(amount / changeArray[i]);
    amount -= (changeArray[i] * changeAmount);

    result.push(changeAmount);

  }
  return result;
}

computeChange([50, 25, 10, 5, 1], 137); //  [2, 1, 1, 0, 2]

answered Aug 26, 2018 at 5:01

Orelongz

465 bronze badges

Comments

Nina Scholz · Accepted Answer · 2015-06-27 17:27:09Z

0

Some remarks:

You get values for coins and amount. The original function access COINSand AMOUNT even if there is a local copy of this values.
creminder is not necessary, because you have amount.
ccoin is not necessary, because you can directly subtract the value of the selected coin from the amount.

var COINS = [50, 25, 10, 5, 1],
    AMOUNT = 36; //137

function computeChange(coins, amount) {
    var i = 0,
        coincount = coins.map(function () { return 0; }); // returns an array and for each element of coins zero
    while (i < coins.length) {
        while (coins[i] <= amount) {
            amount -= coins[i];
            coincount[i]++;
        }
        i++;
    }
    return coincount;
}
out(JSON.stringify(computeChange(COINS, AMOUNT), null, 4), true);

function out(s, pre) {
    var descriptionNode = document.createElement('div');
    if (pre) {
        var preNode = document.createElement('pre');
        preNode.innerHTML = s + '<br>';
        descriptionNode.appendChild(preNode);
    } else {
        descriptionNode.innerHTML = s + '<br>';
    }
    document.getElementById('out').appendChild(descriptionNode);
}

<div id="out"></div>

edited Jun 27, 2015 at 17:27

answered Jun 27, 2015 at 16:55

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

6 Comments

user5040029 Over a year ago

Hi Nina, i tried in the code. The output became like this: ? Checking your code ...

user5040029 Over a year ago

can you explain what does this code here means by doing this

user5040029 Over a year ago

user5040029 Over a year ago

the moment i put this code and the output became like this:

user5040029 Over a year ago

NUMBER VALUE 0 50 1 25 1 10 0 5 1 1 TOTAL AMOUNT: 36 (total is correct) Checking your code ... Result is correct length array of numbers: Yes Standard change for 36 cents: Yes Standard change for $1.37: Yes Strange coins for 85 cents: Yes Make change with only pennies: Yes

|

Borislav Lukanov · Accepted Answer · 2020-02-25 14:46:55Z

-2

function cc(c, a) {
    for (var ra=[],i=0,r=a; i<c.length; ra[i] = (r/c[i])|0, r -= ra[i]*c[i], i++); 
    return ra;
}

function cc2(c, a) {
    return c.map((c, i) => { var t = (a/c)|0; a -= c*t; return t; })
}

cc([50, 25, 10, 5, 1], 137);  //  [2, 1, 1, 0, 2]
cc2([50, 25, 10, 5, 1], 137); //  [2, 1, 1, 0, 2]

edited Feb 25, 2020 at 14:46

answered Feb 25, 2020 at 13:35

Borislav Lukanov

11 bronze badge

Collectives™ on Stack Overflow

Greedy Algorithm in JavaScript

4 Answers 4

1 Comment

Comments

6 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

Comments

6 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related