动态规划和贪心算法都是一种推导算法
均用“局部最优解”来推导“全局最优解”
是对遍历解空间的一种优化
当问题具有最有子结构时，可用都动规，而贪心是动规的特例
什么是贪心策略
顾眼前-->长远
-遵循某种规则，不断（贪心地）选取当前最优策略，最终找到最优解
-难点:当前最优未必是整体最优
贪心策略例1:硬币支付问题
有1元，5元，10元，50元，100元，500元地硬币各c1,c5,c10,c50,c100,c500枚
现在要用这些硬币来支付A元，最少需要多少枚硬币?
假定本题至少存在一种支付方案
0<=ci<=10^9
0<=A<=10^5
输入:
第一行有六个数字，分别代表从小到大6种面值地硬币的个数
第二行为A，代表需支付的A元
样例:
输入
3 2 1 3 0 2
620
输出
保持一个分支
static int f(int A,int cur){
if(A<=0)return 0;
if(cur==0)return A;
int coinValue=coins[cur];
int x=A/coinValue;//金额有多少个coinValue
int cnt=cnts[cur];//当前面值的硬币cnt个
int t=min(x,cnt);//若是需要x个coinValue硬币，并且有足够数量，则取走x个
//若是硬币数量不足，则只取走全部数量的硬币
return t+f(A-t*coinValue,cur+1);//用t个当前面值，剩下的继续处理
}//有较小面值的硬币兜底
贪心策略例2:快速过河
一队人（N个人）期望跨河，有一条船，一次只能载2个人，过河之后需要有一个人划回来，所有人才能够跨河，每个人划船速度都不同，两个人一组整体速度是由划船速度较慢的决定的。问题：确定一种策略用最少的时间所有人都能过河。
输入：
方案数：T（1<=T<=20）
人数:N<1000
速度：<100s
输出：
最少的时间
样例：
输入：
1
4
1 2 5 10
输出
17
a,b,c,d
->a,b ->a,d
<-a <-a
->c,d ->a,c
<-b <-a
->a,b ->a,b
a+3b+d 2a+b+c+d
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int T=sc.nextInt();
for(int i=0;i<T;i++){
int n=sc.nextInt();
int[] speed=new int[n];
for(int j=0;j<n;j++){
speed[j]=sc.nextInt();
}
//排序
Arrays.sort(speed);
f(n,speed);
}
}
private static void f(int n,int[] speed){
int left=n;
int ans=0;
while(left>0){
if(left==1){//还剩一人
ans+=speed[i];
break;
}else if(left==2){//还剩两人
ans+=speed[1];
break;
}else if(left==3){//还剩三人
ans+=speed[2]+speed[0]+speed[1];
break;
}else{//大于三个，不断送两个过去，直到还剩下1或2或3个
//先1，2过河，然后让1回来，再让最后两个最大的和倒数第二大的过去，然后2返回来，这样就1，2还在原地，但是最大的两个已经过去了
//和用1作为引导最后两个过河的时间做比较，选最优策略。
//每次都只送最大的那两个过和
//1,2出发，1返回，最后两人出发，2返回
int s1=speed[1]+speed[0]+speed[left-1]+speed[1];
//1,3出发。1返回，1,4出发，1返回
int s2=speed[left-1]+speed[left-2]+2*speed[0];
ans+=min(s1,s2);
left-=2;//左侧作为起点，left代表左侧的剩余人数
}
}
System.out.println(ans);
}
贪心策略例题3:
区间调度问题
有n项工作，每项工作，分别在si时间开始，在ti时间结束
对于每项工作，你想可以选择参与否，如果选择了参与，那么自始至终都必须全程参与
此外，参与工作的时间段不能重复（即使是开始的瞬间的重叠也是不允许的）
你的目标是参与尽可能多的工作，那么最多能参与多少项工作呢？
1<=n<=100000
1<=si<=10^9
输入:
第一行:n
第二行:n个整数空格隔开，代表n个工作的开始时间
第三行:n个整数空格隔开，代表n个工作的结束时间
1--3 4---7 8--10
-------------------->
2---5 6---9
找结束时间最早的
按ti结束时间排序，面向对象
排完序后，找下一个大于上一个结束时间的起始时间
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[] s=new int[n];
int[] t=nwe int[n];
Job[] jobs=new Job[n];
for(int i=0;i<n;i++){
s[i]=sc.nextInt();
}
for(int i=0;i<n;i++){
t[i]=sc.nextInt();
}
for(int i=0;i<n;i++){
jobs[i]=new Job(s[i],t[i]);
}
//按结束时间排序
Arrays.sort(jobs);
int res=f(n,jobs);
System.out.println(res);
}
//从结束时间较早的开始找，按序找下一个开始时间大于上一个的结束时间的元素
//找到后，更新结束时间，继续上述操作
private static int f(int n,Job[] jobs){
int cnt=1;
int y=jobs[0].t;
for(int i=0;i<n;i++){
if(jobs[i].s>y){
cnt++;
y=jobs[i].t;
}
}
return cnt;
}
}
//必须实现排序规则
public static class Job implements Comparable<Job>{
int s;
int t;
public Job(int s,int t){
this.s=s;
this,t=t;
}
public int compareTo(Job other){
int x=this.t-other.t;
if(x==0)
return this.s-other.s;
}else{
return x;
}
}
区间选点问题
给你几个线段，每个线段必须至少有多少个点位穿过，问至少需要几个点位
public class Case_区间选点{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
interval[] intervals=new interval[n];
for(int i=0;i<n;i++){
intervals[i]=new Inteval(sc.nextInt(),sc.nextInt(),sc.nextInt());
}
Arrays.sort(intervals);//按区间右键点排序
int max=interval[n-1].t//右键最大值
int[] axis=new int[max-1];//标记数轴上的点是否已经被选中
for(int i=0;i<=n;i++){
//查阅区间中有多少个点
int s=intervals[i].s;//起点
int t=intervals[i].t;//终点
int cnt=sum(axis,s,t);//sums[t]-sums[s-1];//效率低
//2.如果不够，从区间右键开始标记,遇标记过的就跳过
intervals[i].c-=cnt;//需要新增点的数量
while(interval[i].c>0){
if(axis[t]==0){//从区间终点开始选点
axis[t]=1;
//updateSums(t,sums);//更新前缀和
intervals[i].c--;
t--;
}else{//已经有这个点
//跳过这个点
t--;
}
}
}
System.out.println(sum(axis,0,max));
}
private static void updateSum(int t,int[] sums){
for(int i=t;i<sums.length;i++){
sums[i]++;
}
}
}
private static class Interval implenments Compareble<Interval>{
int s;
int t;
int c;
public interval(int s,int t,int c){
this.s=s;
this.t=t;
this.c=c;
}
public int compareTo(Interval ){
int x=this.x-other.x;
if(x==0){
return this.s-other.s;
}else{
retrun x;
}
}
}
//也可用前缀和来表示，类似于树状数组
//区间和，前缀和->树状数组
区间覆盖问题
覆盖线段最少需要多=少区间来进行覆盖
找小于这个线段起点的所有区间，在这些区间里找终点最长的那一个区间，然后更新线段的起点start=上一个end+1，继续之前的操作，直到完全覆盖这个线段
start start start
|---------------------|
|----|
|----| end
|--------| end
|----| |-------------|
|-------||--------| |---------|
最后+1就行
public class Case_区间覆盖{
public static void main(){
Scanner sc=new Scanner(System.in);
int N=sc.nextInt();
int T=sc.nextInt();
Job[] jobs=new Job[N];
for(int i=0;i<N;i++){
jobs[i]=new Job(sc.nextInt(),sc.nextInt(),sc.nextInt());
}
Arrays.sort(jobs);
int start=1;
int end=1;
int ans=1;
for(int i=0;i<N;i++){
int s=jobs[i].s;
int t=jobs[i].t;
if(i==0&&s>1)break;//没有覆盖线段前面一部分的区间
if(s<=start){
end=max(x,end);//更新更右的端点
}else{//开始下一个区间
ans++;//上一个目标覆盖已经完成
start=end+1;//更新起点，设置一个新的覆盖起点
if(s<=start){
end=max(t,end);//找最远右端点
}else{//若是区间之间有空白，即一个区间结束，找不到下一个小于起点的区间，则直接退出
break;
}
}
if(end>=T){//超越了，线段最右端，全部覆盖，直接退出
break;
}
}
//所有区间都遍历完成,为完全覆盖
if(end<T)
System.out.println(-1);
else
System.out.println(ans);
}
}
private static class Job implements Compareble<Job>{
int s;
int t;
public Job(int s,int t){
this.s=s;
this.t=s;
}
//按照区间起点排序
public int compareTo(Job other){
int x=this.x;
int y=this.y;
}
if(x==0){
return this.t-other.t;
}else{
return x;
}
}
贪心策略例4:字典序最小问题
给定一个定长为N的字符串S，构造一个字符串T.长度也为N
起初，T是一个空串，随后反复进行下列任意操作
1，从S的头部删除一个字符，加到T的尾部
2，从S的尾部删除一个字符，加到T的尾部
目标是最后生成的字符串T的字典序尽可能小
1<=N<2000
字符串S只包含大写英文字母
输出:字符串T
要求每80个字符换行输出
//ACDBCB-->ABCBCD
//ACDBCB
//BCBDCA
//这题唯一要考虑的就是如果两端相同，选哪端
public class Case_最小最小字典序{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int N=sc.nextInt();
StringBuilder ss=new StringBuilder();
for(int i=0;i<N;i++){
ss.append(sc.next());
}
//String s=sc.nextLine();
f(ss.toString);
}
private static void f(String s){
String s1=new StringBuilder(s).reverse().toString();
int N=s.length();
StringBuilder rs=new StringBuilder();
int cnt=0;
while(rs.length()<N){
if(s.compareTo(s1)<=0){
rs.append(s.charAt(0));
s=s.substring(1);
}else{
rs.append(s1.charAt(0));
s1=s1.subString(1);
}
//字符满80个就换行
if(rs.length()%80==0){
System.out.println(rs.substring(cnt*80),(cnt+1)*80);
cnt++;
}
}
//余数部分
if(rs.length()>cnt*80){
System.out.println(rs.substring(cnt*80));
}
}
}
背包问题及相关问题（最优装在问题，部分背包问题，乘船问题）
给出n个物体，第i个物体重量vi，选择尽量多的物体，使得总重量不超过C
public class Case_最有装载问题{
public static void main(String[] args){
Scanner sc=new Scanner();
int n=sc.nextInt();
int[] w=new int[n];
for(int i=0;i<n;i++){
w[i]=sc.nextInt();
}
int C=sc.nextInt();
Arrays.sort(w);
int ans=f(n,w,C);
System.out.println(ans);
}
private static int f(int n,int[] w,int c){
int sum=0;
int cnt=0;
for(int i=0;i<n;i++){
sum+=w[i];
if(sum<=c){
cnt++;
}else{
break;
}
}
return cnt;
}
}
部分背包问题
给出n个物体，第i个物体重量wi，价值为vi，在总重量不超过C的情况下让总价值尽量高
每个物体不可以只取走有部分，价值和重量按比例计算
求最大总价值
注意:每个物体可以只拿一部分，因此一定可以让总重量恰好为C
public class Case_部分背包问题{
//自己定int C;
public static void main(String[] args){
int[] w={1,2,3,4,5};
int[] v={3,4,3,1,4};
int n=w.length();
Obj[] objs=new Obj[n];
for(int i=0;i<n;i++){
objs[i]=new Obj(w[i],v[i]);
}
Arrays.sort(objs);
int c=C;
int maxValue=0;
for(int i=n-1;i>=0;i--){
if(objs[i].w<=c){
maxValue+=obj[i].v;
c-=objs[i].w;
}else{
maxValue+=objs[i].v*(c/pbjs[i].w);
break;
}
}
}
private static class Obj implements Comparable<Obj>{
int w;
int v;
public Obj(int w,int v){
this.w=w;
this.v=v;
}
public double getPrice(){
return v/(double)w;
}
public int compareTo(Obj o){
if(this.getPrice()==o.getPrice())return 0;
else if(this.getPrice()<o.getPrice())return -1;
else return 1;
}
}
}
乘船问题
有n个人，第i个人重量为wi,每艘船的最大载重量均为C,且最多只能乘两人。用最少的船装在所有人。
贪心策略，考虑最轻的人i,如果每个人都无法和他一起坐船（重量和超过C），则唯一的方案是每个人坐一艘
求需要船的数量
public class Case_乘船问题{
public static void main(String[] args){
int[] w={1,2,3,4,5,6,7,8,9,10};
int n=w.length;
int c=10;
Arrays.sort(w);
int cntOfperson=n;
int cntOfBoot=0;
int p1=0;
int p2=n-1;
while(cntOfperson>0){
if(p1+p2>c){//大的自己一艘，先走
p2--;//大指针左移
cntOfperson--;//剩余的人数-1
cntOfBoot++;//船数+1
}else{//小的加大的可以一起走
p1++;//小指针右移
p2--;//大指针左移
cntOfperson-=2;//剩余的人数-2
cntOfBoot++;//船数+1
}
}
System.out.println(cntOfBoot);//最后输出船数
}
}
贪心策略小结
-最优子结构:对比dfs,不是进行各种可选支路的是试探，而是当下
就可用某种策略决定选择，无需考虑未来（未来情况的演变也影响不了当下的选择）
-只要一直这么选下去，就能得出最优的解，每一步都是当下（子问题）的最优解，
结果是原问题的最有解，这叫做最优子结构
-更书面的说法:如果问题的一个最优解中包含了子问题的最有解，则该问题具有最优子结构
-具备这类结构的问题，可以用局部最优解来推导全局最有解，可以认为是一种剪枝法,是对"df遍历法"的优化
贪心:由上一步的最优解推导下一步的最优解，而上一步之前的（历史）最优解则不作保留//（选当下最优的选项，然后继续如此）
