zuo-算法-贪心算法

例题8；
初始资金是1，最多可做4个项目，怎样安排才能使最后的利润最大

方法：根据花费建立小根堆 ，把所有项目放入小根堆(这些叫做锁定项目);初始资金是1，把初始资金<=1的项目弹出放入大根堆（按照利润建立），就是弹出（1,1）和（1,4）((这些叫做解锁项目))，则（1,4）在（1,1）的上面，大根堆里弹出（1,4），此时初始资金就变为5，然后再把小根堆里初始资金<=5的项目弹出放入大根堆，

public class CostProfix {public static class Node{public int profit;public int cost;public Node(int p,int c) {this.profit=p;this.cost=c;}}public static class MinCostComparator implements Comparator<Node>{//按照花费组织的小根堆的比较器@Overridepublic int compare(Node o1, Node o2) {// TODO 自动生成的方法存根return o1.cost-o2.cost;}} public static class MaxProfitComparator implements Comparator<Node>{//按照利润组织的啊大根堆的比较器@Overridepublic int compare(Node o1, Node o2) {// TODO 自动生成的方法存根return o2.profit-o1.profit;}}//k指最多串行做k个项目，m表示初始资金，最终输出获得的最大钱数public static int findMaxMoney(int k,int m,int[] profits,int[] costs) {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],costs[i]));}//进行K轮，因为最多串行k个项目for(int i=0;i<k;i++) {//能力所及的项目，全解锁while(!minCostQ.isEmpty()&&minCostQ.peek().cost<=m) {maxProfitQ.add(minCostQ.poll());}if(maxProfitQ.isEmpty()) {return m;}m+=maxProfitQ.poll().profit;}return m;}public static void main(String[] args) {int k=4;int m=1;int[] costs= {1,1,2,2,3,4};int[] profits= {1,4,3,7,2,10};int maxmoney=findMaxMoney(k,m,profits,costs);System.out.println(maxmoney);}
}

运行结果

这个也是大根堆小根堆相结合的例子
方法：（1）给定的数如果小于大根堆堆顶，入大根堆；如果不是就入小根堆（2）比较大根堆与小根堆的size大小，如果相差等于2，就把size较大的那个堆顶弹出进入size较小的那个堆。
这样的话较小的n/2个数放在了大根堆了，较大的n/2 个数放在了小根堆里

n皇后问题

/*n皇后问题*/
public class NHuangHou {public static int num1(int n) {if(n<1) {return 0;}int[] record=new int[n];//record[i]表示i行的皇后放在了第几列return process(0,record,n);}//i表示目前来到了第i行//record【0...i-1】表示之前的行，放的皇后位置（任何两个皇后一定不工共行不共列不共斜线）//n表示整体一共有多少行//返回值是，摆完所有的皇后，合理的摆法有多少种public static int process(int i, int[] record, int n) {if(i==n) {//终止行return 1;}int res=0;for(int j=0;j<n;j++) {//当前行在i行，尝试i行所有列//当前i行的皇后，放在j列，会不会和之前（0...i-1）的皇后，共行共列或共斜线//如果是，认为有效//如果不是，认为无效if(isValid(record,i,j)) {//之前放的所有皇后，都不要与i行j列的皇后冲突record[i]=j;//如果都不冲突，才能放res+=process(i+1,record,n);//然后去i+1行放皇后}//System.out.print(res+" ");//测试}//System.out.print(res+" ");//测试return res;}//record【0...i-1】需要看，record【i...】不需要看//返回i行皇后，放在j列，是否有效public static boolean isValid(int[] record, int i, int j) {for(int k=0;k<i;k++) {//之前某个K行的皇后if(j==record[k]||Math.abs(record[k]-j)==Math.abs(i-k)) {//j==record[k]检查是否共列，Math.abs(record[k]-j)==Math.abs(i-k)检查是否共行（列坐标的绝对值是否等于行坐标的绝对值）return false;}}return true;}public static void main(String[] args) {int result=num1(5);System.out.println(result);}
}