贪?算法是?种求近似解的思想。当能满??部分最优解时就认为符合逻辑要求。
还?找零 这个案例为例, 考虑使?贪?算法解题: ?如当找零数为 36 时, 从硬币数的最?值 20 开始填充,
填充不下后再? 10 来填充, 以此类推, 找到最优解。
场景: 假如有 1, 5, 10, 20,50,100 的??币
36 // 找零数
[20, 10, 5, 1] // 需 20、10、5、1
class Change {
constructor(changeType){
this.changeType = changeType.sort((r1, r2) => r2 - r1)
}
makeChange(amount) {
const arr = []
for (let i = 0; i < this.changeType.length; i++) {
while (amount - this.changeType[i] >= 0) {
arr.push(this.changeType[i])
amount = amount - this.changeType[i]
}
}
return arr
}
}
const change = new Change([1, 5, 10, 20,50,100])
console.log(change.makeChange(36))
console.log(change.makeChange(136))
console.log(‘-‘.repeat(100))
const change1 = new Change([1, 3, 4])
console.log(change1.makeChange(6)) // 其实33最好
贪?算法相对简单，就是先怼最?的，?部分情况都OK，但是有些情况不是最优解，所以?不要太贪
?哦
console.log(‘-‘.repeat(100))
const change1 = new Change([1, 3, 4])
console.log(change1.makeChange(6)) // 其实33最好
算法 对贪?算法对研究
原文：https://www.cnblogs.com/zhouyideboke/p/13047157.html
