JavaScript中的贪婪算法
Greedy Algorithm in JavaScript
以下是我需要咨询以获得帮助的问题：
编写一个贪婪算法，以尽可能少的硬币进行更改使用贪婪算法。您将获得一组硬币值数量：CCD_ 1。返回一个带有每枚硬币的计数。
例如：
computeChange([50, 25, 10, 5, 1], 137)应返回表示每枚硬币的数量的数组CCD_ 3：250美分硬币、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 = "answerswer">?</div></p>
<br>
<script>runSolution();</script>
</body>
</html>
想法：在阅读了回复之后，首先想到的是，这可能会用于我们在这里没有看到的其他代码，所以我们需要使函数足以通过输入来解决问题，而不是使用AMOUNT、COINS和coincount这样的GLOBAL VALUES，而是使用computeChange(coins, amount)0和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帐户，所以当您的函数生成结果集时，这很重要。
虽然上面的答案非常正确，但我认为人们也可以用不同的方式来思考这个特定问题的解决方案。
以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的值。原始功能访问CCD_ 24和CCD_。 -
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>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]
相关文章：
- 循环比赛位置算法
- javascript扫雷器floodfill算法不能正常工作
- Node JS中的排名系统算法
- 查找仅适用于原始图像的图像放大算法的名称
- 在数组的 2/3 上调用自身的排序算法
- Luhn算法的实现
- 算法:从数组(javascript/angular）中按当前日期获取上一个和下一个事件
- 加速单纯形算法
- 最短路径算法js错误
- 代码战争中的算法混乱
- 用于自动放置流程图形状的算法
- PHP或JavaScript的基本遗传算法开源代码
- 用Javascript实现算法
- 堆中for循环的奇怪行为's算法
- 一种从随机数的序列中查找值的简单算法
- dropable的Over事件是't工作正常，在可拖动对象被拖放到贪婪的可拖动对象上并再次拖动后
- Node.js上的高性能算法
- youtube视频的正则表达式匹配模式可以以非贪婪的方式完成吗
- JavaScript排序算法不起作用 - 任何明显的我做错了
- JavaScript中的贪婪算法
