贪婪算法和实例
贪婪算法
作者：Sunny_kπ
算法思路
从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快地求解
当算法中的某一步不能再继续前进时，就停止算法，给出就近似值
缺点：
不能保证最后的解是最优的
不能用来求解最大最小解的问题
只能求满足某些约束条件的可行解服务
const MAXN = 9;
let parvalue = [10000, 5000, 1000, 500, 200, 100, 50, 20, 10];
let num = [];
for(let i = 0; i < MAXN; i++){
num[i] = 0;
}
function exchage(n){
var i,j;
for(i = 0; i parvalue[i]) break; // 找到比n小的最大面额
while (n > 0 && i = parvalue[i]){
n -= parvalue[i];
num[i]++;
}else if(n = 5){
num[MAXN - 1]++;
break;
}else{
i++;
}
}
}
function main(){
let i,m;
m = +prompt('请输入要找零的金额');
exchage(100 * m);
console.log(`${m}元找零的组成：`);
for(i = 0; i 0)
console.log(`${(parvalue[i]/100)}:${num[i]}张`)
}
}
main();
作者：Sunny_kπ
