【算法】贪心法

贪心法"/>

【算法】贪心法

贪心法

• 贪心算法
• 特征
• 基本思路
• 举个例子（硬币问题）

贪心算法

贪新算法通过一系列的选择来得到问题的解。他所做的每一个选择都是当前状态下的最好选择，即贪心选择。
贪心选择的一般特征：贪心选择和最优子结构性质。

特征

一、贪心选择性质
贪心选择性质是指所求的问题的整体最优解可以通过一系列局部最优的选择，即贪心选择。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
在动态规划算法中，每步所做的选择往往依赖于相关子问题的解。因而只有在解出相关子问题后，才能做出选择。而贪心算法中，仅在当前状态下选取做出最好的选择，即局部最优选择。
然后再去解出做出这个选择后产生的相应的子问题。贪心算法所作出的选择可以依赖于以往做出的选择，但绝不依赖于将来做出的选择，也不依赖于子问题的解。正是由于这种差别，动态规划算法通常以自底向上的方式解各个子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相应的贪心选择，每做一次贪心选择就将所求问题简化为规模更小的子问题。
对于一个具体的问题，要确定他是否具有贪心选择性质，必须证明每一步所做的贪心选择最终导致问题的整体最优解。
二、最优子结构性质
当一个问题的最优解包含子问题的最优解时，称此问题具有最优子结构性质。

基本思路

①建立数学模型来描述问题。
②把求解的问题分成若干个子问题。
③对每一子问题求解，得到子问题的局部最优解。
④把子问题的解局部最优解合成原来解问题的一个解。

举个例子（硬币问题）

【例题】有1元、5元、10元、50元、100元、500元硬币若干枚，现在要用这些硬币来支付A元，求最少需要多少枚硬币？假定至少存在一种方案(0≤硬币数量≤10^{9，0≤A≤10}9)。
【思路】显然用每次用最大的面值就可以达到最小，因此为贪心法

//硬币问题
import java.util.Scanner;
public class test{/*java创建数组有两种方法1` int coin[] = {1,2,3,4,5,6};2` int[] coin = new coin[10];*/public static void main(String[] args){int a;//找零总价int total = 0;//硬币个数int now;//临时变量（能选取当前面值的个数）int coin[]={500,100,50,10,5,1};//有几种面值System.out.println("请输入价格：");Scanner scanner = new Scanner(System.in);a = scanner.nextInt();for(int i=0;i<=5;i++){now = a/coin[i];total = total + now;a = a-now*coin[i];if(a == 0)break;}System.out.println("最少硬币个数："+total);}
}