贪心算法

Question

我正在写一段代码，当用户输入所欠的找零金额时，returns 等于该找零的最小硬币数量。例如，假设只使用 25 美分、10 美分、镍币和便士。您输入 1.00 美元。我的代码将在屏幕上呈现的数字是 4（4 个季度等于一美元）。但是，我遇到了一个小错误。例如，如果您输入 $0.41，您希望代码再次呈现 4（1 季度 + 1 角钱 + 1 镍 + 1 便士是等于 41 美分的最小排列量），但它不会呈现5.44.请帮忙！提前谢谢你。

document.write("Hi,how much change is due? ");

function greed () {
 
 var n = document.getElementById('change').value;
 
 if (n >=0)
 { 
  
 
  function amount (amt){
   
    return amt/25 + (amt%25)/10 + ((amt%25)%10)/5 + ((amt%25)%10)%5;
    
    }
  document.write(amount(Math.round(n*100)));
 }
 else {alert("Invalid Amount!")};
}

<!DOCTYPE html>

<html lang="en-US">

 <head>

  <title>Greedy! </title>
  <script type="text/javascript" src="greedy.js" ></script>
 </head>

 <body>
  <form>
   <fieldset>
    <input type="number" id="change" name="change" value="0"/>
    <input type="submit" id="submit" name="submit" value="submit" onclick="greed();"/>
  
   </fieldset>
  </form>
 </body>

</html>

Answer 1

这里的主要问题是您没有将数字视为整数，所以到处都是小数。让我们使用您的示例 (0.41):

amt = n*100 = 41，让我们去return:

return amt/25 + (amt%25)/10 + ((amt%25)%10)/5 + ((amt%25)%10)%5

与

相同

return 41/25 + (41%25)/10 + ((41%25)%10)/5 + ((41%25)%10)%5

如您所知，41/25 =/= 1，与 (41%25)/10 = 16/10 =/= 1 和 ((41%25)%10)/5 = (16%10)/5 = 6/5 =/= 1 相同，但您在代码中不关心这一点，因此您最终将这些十进制数相加直到结束，得到奇怪的值。

您必须使用 parseInt() 来获取整数值，因此它应该如下所示：

return parseInt(amt/25) + parseInt((amt%25)/10) + parseInt(((amt%25)%10)/5) + ((amt%25)%10)%5

为了证明它有效：

document.write("Hi,how much change is due? ");

function greed () {
 
 var n = document.getElementById('change').value;
 
 if (n >=0)
 { 
  
 
  function amount (amt){
   
    return parseInt(amt/25) + parseInt((amt%25)/10) + parseInt(((amt%25)%10)/5) + ((amt%25)%10)%5;
    
    }
  document.write(amount(Math.round(n*100)));
 }
 else {alert("Invalid Amount!")};
}

<!DOCTYPE html>

<html lang="en-US">

 <head>

  <title>Greedy! </title>
  <script type="text/javascript" src="greedy.js" ></script>
 </head>

 <body>
  <form>
   <fieldset>
    <input type="number" id="change" name="change" value="0"/>
    <input type="submit" id="submit" name="submit" value="submit" onclick="greed();"/>
  
   </fieldset>
  </form>
 </body>

</html>

贪心算法

Greedy Algorithm

javascript

greedy