JavaScript中的贪婪算法
以下是我需要咨询以寻求帮助的问题：
编写一个贪婪算法，使用贪婪算法以尽可能少的硬币进行兑换。您将获得一个硬币值数组和一个金额：computeChange（硬币，金额）。返回一个包含每个硬币计数的数组。
例如：computeChange（[50, 25, 10, 5, 1]，137）应该返回数组[2, 1, 1, 0, 2]，该数组指示每枚硬币的数量：2枚50美分硬币，1枚25美分硬币，1枚10美分硬币），没有镍币（5美分），和2便士（1美分），加起来是137美分。
从computeChange返回的数组应该与第一个参数（硬币）的长度相同。假设硬币以递减顺序包含不同硬币类型的值。
贪婪算法说，你反复寻找小于或等于剩余金额的最大硬币，然后从剩余金额中减去该硬币。当剩余金额达到零（或更少）时，返回使用的硬币计数。（此算法并不总是最优的。）
您可以更改变量硬币，该变量给出了可用于进行更改的不同硬币的值，以及金额，该变量是要进行更改的总值。更改这些值可能有助于调试程序。
这是我的代码，我做了，但它没有显示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个答案
虽然上面的答案非常正确，但我认为人们也可以用不同的方式来思考这个特殊问题的解决方案。
以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]
一些评论：
>
你得到硬币和数量的值。原始函数访问COINS和AMOUNT，即使有此值的本地副本。
creminder是不必要的，因为您有金额。
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>
思路：阅读回复后，首先想到的是，这可能会用于我们在这里没有看到的其他代码，所以我们需要使函数足以通过输入来解决问题，而不是使用GLOBAL VALUES，如AMOUNT，COINS和coincount，取而代之的是，使用给定的参数，如硬币和金额，并返回自己创建的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决定的，所以不管我叫computeChange（COINS，AMOUNT）还是computeChange（COINS，37），结果都是一样的，因为37在第二个例子中没有使用，忽略并且creminder仍然设置为AMOUNT。尼娜·斯科尔斯和我所做的都是建立给定的金额帐户，所以当你的函数生成结果集时很重要。
-
本文向大家介绍贪婪算法相关面试题，主要包含被问及贪婪算法时的应答技巧和注意事项，需要的朋友参考一下 参考回答： 贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法。贪婪算法所得到的结果往往不是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果。贪婪算法并没有固定的算法解决框架，算法的关键是贪婪策
-
有人有线索为什么它对案件2不起作用吗？非常感谢你的帮助。编辑：案例2的预期结果是6130美元。我好像得到了6090美元。
-
任务是典型的背包问题。求解时应采用贪婪算法。我设法创建了下面的代码，但它工作得太慢了。你能告诉我怎么加快速度吗？谢谢你。 c是背包的重量限制。n表示价格权重对的数量（这两个数字都是int类型，而不是float）。限制如下：（1）如果在相同重量的元素之间选择，价格最高的元素应该被取；（2）如果在相同价格和相同重量的元素之间选择，第一个输入的元素应该被取。
-
设计算法以实现给定问题的最佳解决方案。 在贪婪算法方法中，决策是从给定的解决方案域做出的。 由于贪婪，选择了似乎提供最佳解决方案的最接近的解决方案。 贪心算法试图找到一个本地化的最优解决方案，最终可能导致全局优化的解决方案。 但是，通常贪婪算法不提供全局优化的解决方案。 计数硬币 这个问题是通过选择最不可能的硬币来计算到期望的值，并且贪婪的方法迫使算法选择最大可能的硬币。 如果我们提供₹1,2,5
-
贪婪 vs 不贪婪 当重复一个正则表达式时，如用 a*，操作结果是尽可能多地匹配模式。当你试着匹配一对对称的定界符，如 HTML 标志中的尖括号时这个事实经常困扰你。匹配单个 HTML 标志的模式不能正常工作，因为 .* 的本质是“贪婪”的 #!python >>> s = '<html><head><title>Title</title>' >>> len(s) 32 >>> print re.
-
首先，是的，这是我的硬件，我觉得很难，所以我真的很感激一些指导。 我需要证明对于当