算法详解之贪心
贪心算法
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。一个好的贪心策略，能让你事半功倍。
使用条件
利用贪心法求解的问题应具备如下2个特征 [4] 。
1、贪心选择性质
一个问题的整体最优解可通过一系列局部的最优解的选择达到，并且每次的选择可以依赖以前作出的选择，但不依赖于后面要作出的选择。这就是贪心选择性质。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解 [4] 。
2、最优子结构性质
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。在实际应用中，至于什么问题具有什么样的贪心选择性质是不确定的，需要具体问题具体分析 [4] 。
常见的用贪心算法解决的问题
1[活动安排问题] 活动安排问题是可以用贪心算法有效求解的一个很好的例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。
设有n个活动的集合e={1，2，…，n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si< fi。如果选择了活动i，则它在半开时间区间[si，fi]内占用资源。若区间[si，fi]与区间[sj，fj]不相交，则称活动i与活动j是相容的。也就是说，当si≥fi或sj≥fj时，活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。
在下面所给出的解活动安排问题的贪心算法中，各活动的起始时间和结束时间存储于数组s和f{中且按结束时间的非减序：．f1≤f2≤…≤fn排列。如果所给出的活动未按此序排列，我们可以用o(nlogn)的时间将它重排。
public class 安排会议 {
public static class Program{
public int start;
public int end;
public Program(int start,int end){
this.end=end;
this.start = start;
}
}
public static class ProgramComparator implements Comparator<Program>{
@Override
public int compare(Program o1, Program o2) {
return o1.end-o2.end;
}
}
public static int bestArrange(Program[] programs,int timePoint){
Arrays.sort(programs,new ProgramComparator());
int result = 0;
for (int i = 0; i < programs.length; i++) {
if (timePoint<=programs[i].start) {
result++;
timePoint = programs[i].end;
}
}
return result;
}
}
2[最小切割问题]
public class 最小切割 {
public static int lessMoney(int[] arr){
PriorityQueue<Integer> pQ = new PriorityQueue<>();
for (int i = 0; i < arr.length; i++) {
pQ.add(arr[i]);
}
int sum = 0;
int cur = 0;
while (pQ.size() > 1) {
cur = pQ.poll()+pQ.poll();
sum += cur;
pQ.add(cur);
}
return sum;
}
public static class MinheapComparator implements Comparator<Integer>{
@Override
public int compare(Integer o1, Integer o2) {
return o1-o2;
}
}
public static void main(String[] args) {
int[] a = new int[]{30,20,10};
System.out.println(lessMoney(a));
}
}
3.[字符串按照字典序排列]
给定n个字符串，请对n个字符串按照字典序排列。
输入描述:
输入第一行为一个正整数n(1≤n≤1000),下面n行为n个字符串(字符串长度≤100),字符串中只含有大小写字母。
输出描述:
数据输出n行，输出结果为按照字典序排列的字符串。
public class 最小逆序 {
public static class MyComparator implements Comparator<String>{
@Override
public int compare(String o1, String o2){
return (o1+o2).compareTo(o2+o1);
}
}
public static String lowestString(String[] strs){
if(strs==null||strs.length==0){
return "";
}
Arrays.sort(strs,new MyComparator());
StringBuilder res = new StringBuilder();//StringBuilder 线程不安全但是效率高
for(int i=0;i<strs.length;i++){
res=res.append(strs[i]);
}
return res.toString();
}
public static void main(String[] args) {
String[] strs1 = {"jibw","ji","bw","jibw","jp"};
System.out.println(lowestString(strs1));
String[] strs2 = {"ba","b"};
System.out.println(lowestString(strs2));
}
}
4.利润最大
public class 最大利润 {
public static class Node{
public int p;//利润
public int c;//花费
public Node(int c,int p) {
this.c = c;
this.p = p;
}
}
public static class MinCostComparator implements Comparator<Node>{
@Override
public int compare(Node o1, Node o2) {
return o1.c-o2.c;
}
}
public static class MaxProfitComparator implements Comparator<Node>{
@Override
public int compare(Node o1, Node o2) {
return o2.p-o1.p;
}
}
public static void main(String[] args) {
int a[] = new int[]{3,1,2,7,5,9};
int b[] = new int[]{1,1,2,5,3,7};
System.out.println(findMaximizedCapital(4, 1, a, b));
}
public static int findMaximizedCapital(int k,int w,int[] Profits,int[] Capital){
PriorityQueue<Node> minCostQ = new PriorityQueue<>(new MinCostComparator());
PriorityQueue<Node> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator());
//所有项目加入到被锁池中，发费组织的小根堆
for (int i = 0; i < Profits.length; i++) {
minCostQ.add(new Node(Profits[i],Capital[i]));
}
for (int i = 0; i < k; i++) {//进行K轮
//能力所及的项目，全解锁
while (!minCostQ.isEmpty() && minCostQ.peek().c <= w) {
maxProfitQ.add(minCostQ.poll());
}
if (maxProfitQ.isEmpty()) {
return w;
}
w+=maxProfitQ.poll().p;
}
return w;
}
}
5.妞妞找工作
/**
* 为了找到自己满意的工作，牛牛收集了每种工作的难度和报酬。牛牛选工作的标准是在难度不超过自身能力值的情况下，
* 牛牛选择报酬最高的工作。在牛牛选定了自己的工作后，牛牛的小伙伴们来找牛牛帮忙选工作，
* 牛牛依然使用自己的标准来帮助小伙伴们。牛牛的小伙伴太多了，于是他只好把这个任务交给了你。
* 每个输入包含一个测试用例。
* 每个测试用例的第一行包含两个正整数，分别表示工作的数量N(N<=100000)和小伙伴的数量M(M<=100000)。
* 接下来的N行每行包含两个正整数，分别表示该项工作的难度Di(Di<=1000000000)和报酬Pi(Pi<=1000000000)。
* 接下来的一行包含M个正整数，分别表示M个小伙伴的能力值Ai(Ai<=1000000000)。
* 保证不存在两项工作的报酬相同。
* 对于每个小伙伴，在单独的一行输出一个整数表示他能得到的最高报酬。如果他找不到工作，
* 则输出0。一个工作可以被多个人选择。
* 测试用例
* 3 3
* 1 100
* 10 1000
* 1000000000 1001
* 9 10 1000000000
*/
public class 牛牛找工作 {
public static class Job{
int money;
int hard;
public Job(int money, int hard) {
this.money = money;
this.hard = hard;
}
}
public static class JobComparator implements Comparator<Job>{
@Override
public int compare(Job o1, Job o2) {
return o1.hard!=o2.hard?(o1.hard-o2.hard):(o1.money-o2.money);
}
}
public static int[] getMoneys(Job[] jobs,int[] ability){
Arrays.sort(jobs,new JobComparator());
//难度为key的工作，最优钱数是多少，有序表
TreeMap<Integer,Integer> map = new TreeMap<>();
map.put(jobs[0].hard,jobs[0].money);
Job pre = jobs[0];//pre 之前组的组长
for (int i = 0; i < jobs.length; i++) {
if (jobs[i].hard!=pre.hard&&jobs[i].money>pre.money) {
pre=jobs[i];
map.put(pre.hard,pre.money);
}
}
int res[] = new int[ability.length];
for (int i = 0; i <res.length ; i++) {
Integer key = map.floorKey(ability[i]);
res[i] = key!=null?map.get(key):0;
}
return res;
}
public static void printArray(int[] arr){
int length = arr.length;
for (int i = 0; i < length; i++) {
System.out.println(arr[i]);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
Job[] jobs = new Job[n]; //定义一个Job对象数组，用来保存所有工作的能力值和薪资
for (int i = 0; i < n; i++) {
int hard = sc.nextInt();
int money = sc.nextInt();
Job job = new Job(money, hard);//定义一个Job对象，用来保存工作的能力值和薪资
jobs[i] = job;
}
int[] arr = new int[m];//接收找工作的人的能力
for (int i = 0; i < m; i++) {
arr[i] = sc.nextInt();
}
printArray(getMoneys(jobs,arr));
}
}
|