贪心算法

概述

• 最优解问题（贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。）
• 从局部最优到整体最优。
• 无后效性
• 和dp之间的联系（比如完全背包问题，既可以用贪心，也可以用dp）

相关题目

数列分段

对于给定的一个长度为N的正整数数列Ai​，现要将其分成连续的若干段，并且每段和不超过M（可以等于M），问最少能将其分成多少段使得满足要求。
输入格式
第1行包含两个正整数N,M，表示了数列Ai​的长度与每段和的最大值，第2行包含N个空格隔开的非负整数Ai​，如题目所述。
输出格式
一个正整数，输出最少划分的段数

分析

代码

import java.util.*;
public class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();//数列长度
        int m = sc.nextInt();//区间和
        int[] a = new int[n];
        int counter = 1;//段数
        int sum = 0;//现有段的和
        for(int i=0;i<n;i++) {
            a[i] = sc.nextInt();
            if(sum+a[i]<=m) {
                sum+=a[i];
            }else {
                sum = a[i];
                counter++;
            }
        }
        System.out.println(counter);
    }
}

纪念品分组

为使得参加晚会的同学所获得的纪念品价值相对均衡，要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品， 并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，希望分组的数目最少。
输入格式
共 n+2 行：
第一行包括一个整数 w，为每组纪念品价格之和的上上限。
第二行为一个整数 n，表示购来的纪念品的总件数 G。
第 3∼n+2 行每行包含一个正整数 Pi 表示所对应纪念品的价格。
输出格式
一个整数，即最少的分组数目

分析

排序很关键

代码

import java.util.*;
public class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int w = sc.nextInt();//价值上限
        int n = sc.nextInt();//纪念品总件数
        int counter = 0;//组数
        int left = 0;
        int[] p = new int[n];
        for(int i=0;i<n;i++) {
            p[i] = sc.nextInt();
        }
        //排序
        Arrays.sort(p);
        while(left<=n-1) {
            if((p[n-1]+p[left]>w)) {
                counter++;
            }else{
                left++;
                counter++;
            }
            n--;
        }
        System.out.println(counter);
    }
}

最优装载问题

• 给出N个物体，第i个物体重量为Wi。
• 选择尽量多的物体，使得总重量不超过C。

分析

• 尽量多装质量小的
• 是否正确
• 假如我们没有优先装质量小的，我们始终可以把它换成质量更小的。
• 可以确定，只需按从小到大的顺序排列，依次装入，直到装不下为止，即可得到最优解

代码

合并果子

• 有N堆果子（不同种类），每堆果子有自己的果子数Ai，每次合并可以将任意两堆合并，合并消耗的体力为两堆果子数之和。
• 求消耗的最小体力？
• 1 ≤ n ≤ 10000

分析