动态规划和贪心算法都是一中递推算法,均用局部最优解
来推导全局最优解
是对遍历解空间
的一种优化
而dfs是求全部的解
当前问题具有最优子结构
时候可以用动态规划,而贪心是动态规划的特例。
贪心策略是什么
顾眼前
遵循某种规律,不断(贪心地)选取当前最优的策略,最终找到最优解
难点:当前最优未必整体最优
下面看简单例题
硬币问题
有1元,5元,10元,50元,100元,500元的硬币各c1,c5,c10,c50,c100,c500枚.
现在要用这些硬币来支付A元,最少需要多少枚硬币?
假定本题至少存在一种支付方案.
0≤ci≤10^9
0≤A≤10^9
输入说明:
第一行有六个数字,分别代表从小到大6种面值的硬币的个数
第二行为A,代表需支付的A元
输入
3 2 1 3 0 2
620
输出
6
说明:1500+250+110+25,共6枚
代码
当然也可以用循环 ,这里用递归
能用最大面值用多少 剩下的其余硬币组合
然后 求出 最小的需要的面值 就是 min(count[cur], maxGeshu); 这样就不会超过限定的面值 count[cur]
递归注意点就是 最后一个面值是1 所以 币值=面值 这是 一定的
package BlueCup.Eight_DP_greed;
import java.util.Scanner;
import static java.lang.Math.min;
public class 贪心硬币问题 {
static int[] count;
static int[] coin = {1, 5, 10, 50, 100, 500};
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
count = new int[6];
for (int i = 0; i < 6; i++) {
count[i] = cin.nextInt();
}
int value = cin.nextInt();
int ans = f(value, 5);
System.out.println(ans);
}
private static int f(int value, int cur) {
if (value <= 0) return 0;//提前凑够了
if (cur == 0) return value;//面值是1
int maxGeshu = value / coin[cur];//需要
int t = min(count[cur], maxGeshu);// 我有的和我需要的 选出最小的 去换
return t + f(value - t * coin[cur], cur - 1);
}
}
本文地址:https://dxoca.cn/Algorithm/237.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。