贪心算法--经典问题（java实现）

贪心算法--经典问题（java实现）

贪心算法解决经典问题

• 1、贪心算法定义
• 2、基本思想
• 3、简单例子
• • 3.1 分配问题
  • 3.2 区间问题
  • 3.3 快乐司机

1、贪心算法定义

顾名思义，贪心算法或贪心思想采用贪心的策略，保证每次 *** 作都是局部最优的，从而使最后得到的结果是全局最优的。

2、基本思想

通过一系列选择步骤来构造问题的解，每一步都是对当前部分解的一个扩展，直至获得问题的完整解。所做的每一步选择都必须满足：
(1) 可行的：必须满足问题的约束。
(2) 局部最优：当前所有可能的选择中最佳的局部选择。
(3) 不可取消: 选择一旦做出，在后面的步骤中就无法改变了。
举例：
从 1 4 6 9 4 这几个数字中选出三个使得其和最大
先从中选取最大的数字9即求得局部最优解，再依次取出 6 4，最终得到19为全局最优解。

3、简单例子 3.1 分配问题

问题描述：
有一群孩子和一堆饼干，每个孩子有一个饥饿度，每个饼干都有一个大小。每个孩子只能吃最多一个饼干，且只有饼干的大小大于孩子的饥饿度时，这个孩子才能吃饱。求解最多有多少孩子可以吃饱。
输入输出样例：
输入：1 2
输入：1 2 3
输出：2
题解：
因为饥饿度最小的孩子最容易吃饱，所以我们先考虑这个孩子。为了尽量使得剩下的饼干可以满足饥饿度更大的孩子，所以我们应该把大于等于这个孩子饥饿度的、且大小最小的饼干给这个孩子。满足了这个孩子之后，我们采取同样的策略，考虑剩下孩子里饥饿度最小的孩子，直到没有满足条件的饼干存在。
简而言之，这里的贪心策略是，给剩余孩子里最小饥饿度的孩子分配最小的能饱腹的饼干。至于具体实现，因为我们需要获得大小关系，一个便捷的方法就是把孩子和饼干分别排序。这样我们就可以从饥饿度最小的孩子和大小最小的饼干出发，计算有多少个对子可以满足条件。

import java.util.Arrays;
import java.util.Scanner;
public class greedsuanfa {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();//数量
        System.out.println("请输入"+n+"个孩子的饥饿度：");
        Scanner sc = new Scanner(System.in);
        int[] b=new int[n];
        for(int i=0;i=childran数组对应位置元素，childnum++，两个同时向后移动
        // 若cookies元素 
3.2 区间问题 
问题描述：
 给定多个区间，计算让这些区间互不重叠所需要移除区间的最少个数。起止相连不算重叠。
 输入输出样例：
 输入是一个数组，数组由多个长度固定为2的数组组成，表示区间的开始和结尾。输出一个整数，表示需要移除的区间数量。
 输入：[ [1,2], [2,4], [1,3]]
 输出：1
 题解：
 在选择要保留区间时，区间的结尾十分重要:选择的区间结尾越小，余留给其它区间的空间就越大，就越能保留更多的区间。
 因此，我们采取的贪心策略为，优先保留结尾小且不相交的区间。具体实现方法为，先把区间按照结尾的大小进行增序排序([ [1,2], [1,3], [2,4]])，每次选择结尾最小且和前一个选择的区间不重叠的区间。(第一个默认区间为[1,2]，第二个区间 [1,3]，第二个区间起始位置小于第一个区间终止位置，因此，两个区间重叠，跳过该区间后，不重叠，因此需要移除的区间数量为1)
 
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class greedsuanfa {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        System.out.println("输入行数");
        int rows=in.nextInt();//二维数组行数
        System.out.println("输入列数");
        int columns=in.nextInt();//二维数组列数
        int matrix[][] =new int[rows][columns];//定义一个二维数组
        int b=3;
        System.out.println("输入矩阵");
        //从键盘上输入一个二维数组
        for(int i=0;i() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1]-o2[1];
            }
        });
        int count=1;// 满足条件的区间个数
        int pre=matrix[0][1];// pre表示当前区间终止位置元素
        for (int i = 1; i < matrix.length; i++) {
            if (matrix[i][0]>=pre){
                count++;
                pre=matrix[i][1];
            }
        }
        return matrix.length-count;
    }
}

 
3.3 快乐司机 
问题描述：
 　“嘟嘟嘟嘟嘟嘟
 　　喇叭响
 　　我是汽车小司机
 　　我是小司机
 　　我为祖国运输忙
 　　运输忙”
 　　这是儿歌“快乐的小司机”。话说现在当司机光有红心不行，还要多拉快跑。多拉不是超载，是要让所载货物价值最大，特别是在当前油价日新月异的时候。司机所拉货物为散货，如大米、面粉、沙石、泥土…
 　　现在知道了汽车核载重量为w，可供选择的物品的数量n。每个物品的重量为gi,价值为pi。求汽车可装载的最大价值。（n<10000,w<10000,0 输入输出样例：
 输入第一行为由空格分开的两个整数n w，第二行到第n+1行，每行有两个整数，由空格分开，分别表示gi和pi
 输出：
 最大价值（保留一位小数）
 输入：
 5 36
 99 87
 68 36
 79 43
 75 94
 7 35
 输出：
 71.3
 题解：
 先装第5号物品，得价值35，占用重量7，再装第4号物品，得价值36.346,占用重量29，最后保留一位小数，得71.3
 注意 此处4号物品总重75，价值94，物品75可拆分
 
思路
 要使所载货物价值最大，可先计算每件物品的单位价值，每次装载单位价值最大的物品得局部最优解
 
创建n维4列的多维数组arr[n][4]
 
 
import java.util.Scanner;
public class happyDri {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();//数量
        double w = scanner.nextDouble();//重量
        double[][] arr = new double[n][4];
        //第3列为：每一个物品的单位重量的价值
        //第4列为：判断物品是否已经装进车里了，如果装进车里了则为1，还没有装进车为0
        for(int i=0;i0){//当车载重大于0的时候，还可以载物品
            double max=0;
            int index=0;
            boolean flag=true;
            for(int i=0;imax&&arr[i][3]==0){
                    max=arr[i][2];
                    index=i;
                    flag=false;
                }
            }
            arr[index][3]=1;
            if(flag){
                break;
            }
            if(w=arr[index][0]）
                result+=arr[index][1];
                w-=arr[index][0];
            }
        }
        System.out.printf("%.1f",result);
    }
}
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5684921.html