JavaScript中的贪心算法-Java 学习之路

以下是我需要咨询的问题：

使用贪心算法编写一个贪婪的算法，以尽可能少的硬币进行更改 . 您将获得一组硬币值和金额：computeChange（硬币，金额） . 返回一个包含每个硬币计数的数组 . 例如：computeChange（[50,25,10,5,1]，137）应返回数组[2,1,1,0,2]，表示每枚硬币的数量：2个50美分，1个季度（25美分），1毛钱（10美分），没有镍（5美分），2便士（1美分），总计137美分 . 从computeChange返回的数组应该与第一个参数（硬币）的长度相同 . 假设硬币按降序包含不同硬币类型的值 . 贪心算法说你反复寻找小于或等于剩余金额的最大硬币，然后从剩余金额中减去该硬币 . 当剩余金额达到零（或更少）时，返回所用硬币的数量 . （此算法并不总是最优的 . ）您可以更改变量COINS，它可以提供可用于进行更改的不同硬币的值，以及AMOUNT，它是要进行更改的总值 . 更改这些值可能对调试程序很有用 .

这是我的代码，但我没有显示36美分的标准变化 . 谁能帮我？谢谢 .

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

3 回答

1
思考：在阅读完回复之后，首先想到的是这可能会用于我们在这里看不到的其他代码，所以我们需要使函数足以通过输入来解决问题，而不是使用 GLOBAL VALUES ，如 AMOUNT ， COINS 和 coincount ，相反，使用像 coins 和 amount 这样的参数，并返回自己创建的 coincount .

我将在代码中直接解释这一点
```
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;
}
```
您的原始版本的 creminder 由 AMOUNT 确定，因此无论我调用 computeChanges(COINS, AMOUNT) 还是 computeChanges(COINS, 37) ，结果都是相同的，因为第二个示例中的 37 未使用，被忽略且 creminder 仍设置为 AMOUNT . Nina Scholz和我都做的是给出 amount 帐户，所以当你的函数生成结果集时这很重要 .
回复于 2024-04-28T13:47:40+08:00

一些评论：

您获得 coins 和 amount 的值 . 即使存在此值的本地副本，原始函数也会访问 COINS 和 AMOUNT .
creminder 不是必需的，因为你有 amount .
ccoin 不是必需的，因为您可以直接从金额中减去所选硬币的值 .

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>

回复于 2024-04-28T13:47:40+08:00

虽然上面的答案非常正确，但我认为人们也可以用不同的方式思考这个特定问题的解决方案 .

以 computeChange([50, 25, 10, 5, 1], 137) 为例，可以使用单个循环来获得所需的解决方案 .

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]

回复于 2024-04-28T13:47:40+08:00

JavaScript中的贪心算法

3 回答

相关问题