概念
贪心算法又称贪婪算法(greedy algorithm),是一种在每一步选择中都采取在目前状态下最好或最佳(即最有利)的选择,从而希望导致结果是最好或最佳的. 比如在旅行推销员问题中,如果旅行员每次都选择最近的城市,那这就是一种贪婪算法.
贪婪算法在有最佳子结构的问题中尤其有效, 最佳子结构就是说局部最佳解能决定全局最优接, 简而言之, 就是问题能分解成子问题来解决, 子问题的最优解能地推到最终问题的最优接.
贪心算法和动态规划的不同之处在于它对每个子问题的解决方案都作出选择, 不能回退. 动态规划则会储存以前的运算结果,并根据以前的结果对目前进行选择,有回退功能.
贪心算法可以解决一些最佳化问题,如:求图中的最小生成树、求哈夫曼编码等, 对于其他问题,贪心算法一般不能得到我们所要求的答案. 一旦一个问题可以通过贪心算法来解决,那么贪心算法一般是解决这个问题的最好办法. 由于贪心算法的高效性以及其所求得的答案比较接近最佳结果,贪心算法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题.
一般解题步骤
- 建立数学模型来描述问题.
- 把求把的问题分成若干个子问题.
- 对每一子问题求解,得到子问题的局部最佳解.
- 把子问题的局部最佳解合成原来问题的一个解.
代码示例
public static int greedyAlgorithm(int money, int[] count, int[] value) {
int num = 0;
for (int i = N - 1; i >= 0; i--) {
//每一个币值所需要的张数
int c = Math.min(money / value[i], count[i]);
money = money - c * value[i];
//总张数
num += c;
}
if (money > 0) {
num = -1;
}
return num;
}
public static void main(String[] args) {
// 不同面值的钱对应的 张数
int[] count = {5, 2, 2, 3, 5};
// 钱的面值
int[] value = {1, 5, 10, 50, 100};
int moneyCount = greedyAlgorithm(456, count, value);
System.out.println(moneyCount);
}