贪⼼算法是⼀种求近似解的思想。当能满⾜⼤部分最优解时就认为符合逻辑要求。
还⽤找零 这个案例为例, 考虑使⽤贪⼼算法解题: ⽐如当找零数为 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最好