什么是贪心算法？

一、什么是贪心算法

贪心算法是指，在对问题求解时，老是做出在当前看来是最佳的选择。（局部最优解，而不是总体最优解）

贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必需注意的是，贪心算法不是对所有问题都能得到总体最优解，选择的贪心策略必需具备无后效性（即某个状况之后的进程不会影响之前的状况，只与当前状况有关。）所以，对所采取的贪心策略一定要细心分析其是不是知足无后效性。文章源自微观生活（93wg.com）微观生活-https://93wg.com/5737.html

二、贪心算法基本思路

把求解的问题分成若干个子问题文章源自微观生活（93wg.com）微观生活-https://93wg.com/5737.html

对每一个子问题求解，得到子问题的局部最优解（不能保证求得的最后解是最好的）文章源自微观生活（93wg.com）微观生活-https://93wg.com/5737.html

把子问题的解局部最优解合成原来问题的一个解文章源自微观生活（93wg.com）微观生活-https://93wg.com/5737.html

可以看出贪心算法以及动态计划无比类似，然而二者存在部份区分文章源自微观生活（93wg.com）微观生活-https://93wg.com/5737.html

1）贪心算法每一一步的最优解一定包括上一步的最优解，上一步以前的最优解则不作保存。而动态计划全局最优解中一定包括某个局部最优解，但不一定包括前一个局部最优解，因而需要记录以前的所有的局部最优解。文章源自微观生活（93wg.com）微观生活-https://93wg.com/5737.html

2）贪心算法只能求知足某些束缚前提的可行解的规模。文章源自微观生活（93wg.com）微观生活-https://93wg.com/5737.html

3）贪心不能保证求得的最后解是最好的，一般繁杂度低。而动态计划本色是穷举法，可以保证结果是最好的，繁杂度高。文章源自微观生活（93wg.com）微观生活-https://93wg.com/5737.html

三、经典例题

1）指定币值以及相应的数量，用起码的数量凑齐某金额文章源自微观生活（93wg.com）微观生活-https://93wg.com/5737.html

思路：优先选择面值大的钱币，以此类推，直到凑齐总金额文章源自微观生活（93wg.com）微观生活-https://93wg.com/5737.html

public int[] getCoinNum {
int[] result = new int[values.length];

int add = 0;

for {
int num = / values[i];

if {
num = counts[i];
}

add = add + num * values[i];
result[i] = num;
}

return result;
}

2）部份背包问题，物品可以不完整放入包中，求价值最大的方案

思路：选择单位重量价值最高的物品，将尽量多的该物品装入背包，直到背包装满为止。

public float getNum {
float max = 0;

float weight = 0;

for {
if {
max = v[i] / w[i];
weight = w[i];
}
}
float num = M / weight;
return num;
}

以上就是微观生活（93wg.com）关于“什么是贪心算法？”的详细内容，希望对大家有所帮助！