贪心算法例题总结
<font size="6px">
一、硬币支付问题</font>
****题目描述：有1元，5元，10元，50元，100元，500元的硬币各c1，c5，c10，c50，c100，c500枚。现在要用这些硬币来支付A元，最少需要多少枚硬币？
假定本题至少存在一种支付方案
0<=ci<=10^9
0<=A<=10^9
输入：
第一行有六个数字，分别代表从小到大6种面值的硬币的个数
第二行为A，代表需要支付A元
样例：
输入：
3 2 1 3 0 2
620
输出：
6
思路分析：首先按照题目要求进行输入。然后调用递归函数。函数的参数总共有5个参数，第一个参数是总额，num和coins是两个数组，然后current是当前位置。因为要最少的硬币，所以从数组最末开始选取，current开始时是等于5的。然后先获取本轮递归中硬币的币值，然后用总额除以币值获得需要硬币的个数。然后获取硬币实际有多少个。调用函数选取两者中的最小值。继续递归。最后确定递归出口，并输出结果。
//硬币支付问题
public static void main(String[] args) {
Scanner reader=new Scanner(System.in);
int[] num=new int[6];
int[] coins= {1,5,10,50,100,500};
for(int i=0;i<num.length;i++) {
num[i]=reader.nextInt(); //输入每种硬币的个数
}
int A=reader.nextInt(); //输入支付的总额
int answer=Count(A,num,coins,coins.length-1); //调用函数
System.out.println(answer); //输出结果
}
private static int Count(int A, int[] num,int[] coins,int current) {
if(A<=0) { //出口
return 0;
}
int coinsValue=coins[current]; //获取本次循环的硬币值
int temp=A/coinsValue; //看总额要用多少个硬币才能凑出来
int cnt=num[current]; //硬币有多少枚
int t=Math.min(temp, cnt); //运用函数选取两者较小值
return t+Count(A-t*coinsValue,num,coins,current-1); //递归调用
}
<font size="6px">
二、快速渡河问题</font>
****题目描述：有N个人期望去跨越一条河，但是只有一只船，这只船一次最多只能携带两个人。因此一些排列是可以把这艘船运送所有人的往返时间尽可能短的。每个人都有不同的划船速度，两个人一组时的整体速度是由慢的那个人决定的。你的工作就是确定一种策略，用最短的时间将所有人运送过去。
输入输出：
输入的总人数不超过1000，划船速度不超过100
第一行输入总人数，第二行输入每个人的划船速度。
输出最短时间。
样例：
输入：
4
1 2 5 10
输出：
17
思路分析：首先按照题目要求输入每个人的速度，并将速度进行从小到大的排序。然后调用自定义的函数。这道题比较快的两种过河方法分别是：1、永远用速度最快的人带其他人过河。2、先将速度最快的和速度第二快的人一起过河，然后速度最快的返回。然后速度最慢的两个人过河，速度第二快的人返回。通过这两种方式过河，直到最后所有人都通过。
//快速渡河问题
public static void main(String[] args) {
Scanner reader=new Scanner(System.in);
int sum=reader.nextInt();
int[] person=new int[sum];
for(int i=0;i<person.length;i++) {
person[i]=reader.nextInt(); //按题目要求输出每个人的速度
}
Arrays.sort(person); //对速度进行排序
f(sum,person); //调用函数
}
private static void f(int sum,int[] person) {
int left=sum; //尚未过河的总人数
int count=0; //总时间
while(left>0) {
if(left==1) { //如果只有一人未过河
count+=person[0];
break;
}else if(left==2) { //如果有两人未过河
count+=person[1];
break;
}else if(left==3) { //如果有三人未过河
count+=person[1]+person[0]+person[2];
break;
}else { //三人以上未过河
//1和速度最慢的先过河，1返回，1和速度第二慢的 过河，1返回
int temp1=2*person[0]+person[left-1]+person[left-2];
//1、2先过河，1返回，两个最慢的过河，2返回
int temp2=2*person[1]+person[0]+person[left-1];
int judge=Math.min(temp1,temp2); //选取最小值
count+=judge;
left-=2; //人数-2
}
}
System.out.println(count); //输出结果
}
<font size="6px">
三、区间调度问题</font>
****题目描述：有n项工作，每项工作分别在si时间开始，早ti时间结束。对于每项工作，你都可以选择参与与否，如果选择了参与，那么自始至终都必须全程参与。此外，参与工作的时间段不能重复（即使是开始瞬间和结束瞬间的重叠也是不允许的），你的目标是参与尽可能多的工作，那么最多能参与多少工作呢？
1<=n<=10000
1<=si<=ti<=10^9
输入输出：
第一行：n
第二行：n个整数空格隔开，代表n个工作的开始时间
第三行：n个整数空格隔开，代表n个工作的结束时间
样例：
输入：
5
1 2 4 6 8
3 5 7 9 10
输出：
3
思路分析：这道题需要用到面向对象的思想，将一个工作的开始时间和结束时间打包成一个对象。本题将一个工作打包成了一个对象Job，变量包括开始时间begin和结束时间end，实现Comparable方法，按照按照结束时间先后排序。因为本题使用贪心算法，本题的贪心之处在于想要参加更多的工作，那就让每一项工作的结束时间尽可能早，这样后面就能选择更多工作。所以对工作排序时，结束时间早的放在前面。创建完Job对象之后，来到main方法。首先按照题目输入开始和结束时间，并把时间打包成Job对象，然后进行排序。调用自定义的f方法。Job数组中的第一个工作时肯定要接的，所以初始化count=1，current=jobs[0]。然后对数组进行遍历，如果有一个工作的开始时间比current的结束时间晚的，就count++；并且将current=jobs[i];。全部遍历结束之后输出结果。
//区间调度问题
public static void main(String[] args) {
Scanner reader=new Scanner(System.in);
int num=reader.nextInt();
int[] begin=new int[num];
int[] end=new int[num];
Job[] jobs=new Job[num];
for(int i=0;i<num;i++) {
begin[i]=reader.nextInt(); //获取每段开始时间
}
for(int i=0;i<num;i++) {
end[i]=reader.nextInt(); //获取每段结束时间
}
for(int i=0;i<num;i++) {
jobs[i]=new Job(begin[i], end[i]); //封装成一个job对象
}
Arrays.sort(jobs); //按照结束时间的先后进行排序
f(jobs); //调用函数
}
private static void f(Job[] jobs) {
int count=1;
Job current=jobs[0]; //第一段时间是肯定要取的
for(int i=1;i<jobs.length;i++) {
if(jobs[i].begin>current.end) { //选择下一段开始时间大于本次的结束时间的
count++;
current=jobs[i];
}
}
System.out.println(count); //输出结果
}
private static class Job implements Comparable<Job>{ //Job对象，要实现Comparable接口
int begin;
int end;
public Job(int begin,int end) {
this.begin=begin;
this.end=end;
}
@Override
public int compareTo(Job other) { //按照结束先后进行排序，如果结束时间相同，则按开始先后排序
if(this.end!=other.end) {
return this.end-other.end;
}else {
return this.begin-other.begin;
}
}
}
<font size="6px">
四、字典最小序问题</font>
****题目描述：给一个定长为N的字符串S，构造一个字符串T，长度也为N。起初，T是一个空串，随后反复进行下列任意操作
1、从S的头部删除一个字符，加到T的尾部
2、从S的尾部删除一个字符，加到T的尾部
目标是最后生成的字符串T的字典序尽可能小
1<=N<=2000
字符串S只包含大写英文字母
输入：字符串S
输出：字符串T
要求每80个字符换行输出
样例输入：
6
ACDBCB
样例输出：
ABCBCD
思路分析：这道题首先建立输入，然后调用自定义的方法f。String和StringBuilder的一个区别就是StringBuilder可以修改字符串，本题也采用了StringBuilder的append方法。首先创建一个StringBuilder对象，调用reverse方法对字符串s进行反转。然后创建结果字符串answer。建立循环，比较字符串s和s1的字典序，字典序小的，就将0号位上的字符添加到结果字符串中。最后输出结果。
//字典序最小问题
public static void main(String[] args) {
Scanner reader = new Scanner(System.in);
int N = reader.nextInt();
String s = reader.next(); //字符串输入
f(s, N); //调用函数
}
private static void f(String s, int N) {
StringBuilder stringBuilder = new StringBuilder(s); //创建StringBuilder对象
String s1 = stringBuilder.reverse().toString(); //将字符串反转，定义一个新的字符串
StringBuilder answer = new StringBuilder(""); //结果字符串
while (answer.length() < N) { //出口
if (s.compareTo(s1) >= 0) { //如果s的字典序比s1大
answer.append(s1.charAt(0)); //将字符加到结果字符串中
s1 = s1.substring(1); //删除该字符在旧字符串中的位置
} else { //如果s的字典序比s1小
answer.append(s.charAt(0));
s = s.substring(1);
}
if(rs.length()%80==0) {
System.out.println(rs.substring(cnt*80,(cnt+1)*80)); //每80个字符换行输出
cnt++;
}
}
if(rs.length()>cnt*80) {
System.out.println(rs.substring(cnt*80)); //剩余字符输出
}
}
<font size="6px">
五、最优装载问题</font>
题目描述：给出n个物体，第i个物体重量为wi。选择尽量多的物体，使得总重量不超过C
思路分析：这道题较为简单。思路就是每次选择物体最小的。
//最优装载问题
public static void main(String[] args) {
Scanner reader = new Scanner(System.in);
int C = reader.nextInt(); //输入总重量
int n = reader.nextInt(); //输入物体总数
int[] object = new int[n];
for (int i = 0; i < object.length; i++) {
object[i] = reader.nextInt(); //输入每个物体的质量
}
f(object, C); //调用函数
}
private static void f(int[] object, int C) {
Arrays.sort(object); //排序
int count = 0; //计数器
for (int i = 0; i < object.length; i++) {
if (C - object[i] >= 0) { //确定是否越界
count++;
C -= object[i];
} else {
break;
}
}
System.out.println(count);
}
<font size="6px">
六、部分背包问题</font>
题目描述：有n个物体，第i个物体的重量为wi，价值为vi。在总重量不超过C的情况下让总价值尽量高。每一个物体都可以只取走一部分，价值和重量按比例算。
求最大总价值
注意：每个物体可以只拿一部分，因此一定可以让总重量恰好为C
思路分析：这道题其实和前面的区间调度问题的思想是一样的，需要创建一个对象来封装重量w和价值v，本题就创建了一个Obj对象，并实现Comparable接口，进行比价，按照每种物品的单价进行排序。创建完对象之后，将重量数组和价值数组封装在对象中。然后遍历这个数组，如果剩余可装的重量大于当前重量，就总重量count加上对应的价值，最大重量逐步减小。如果剩余可装的重量小于于当前重量，就用(C / objs[i].w)计算还能装入多少个物体，然后count加上价值。最后输出结果
// 部分背包问题
public static void main(String[] args) {
int[] w = { 1, 2, 3, 4, 5 }; //重量数组
int[] v = { 3, 4, 3, 1, 4 }; //价值数组
double C = 10; //最大重量
int n = w.length;
Obj[] objs = new Obj[n];
for (int i = 0; i < n; i++) {
objs[i] = new Obj(w[i], v[i]); //创建Obj对象数组
}
Arrays.sort(objs); //按照价值大小排序s
double count = 0; //总价值
for (int i = objs.length - 1; i >= 0; i--) {
if (objs[i].w <= C) { //如果剩余可装的重量大于当前重量
count += objs[i].v;
C -= objs[i].w;
} else { //如果剩余可装的重量小于于当前重量
count += objs[i].v * (C / objs[i].w);
break;
}
}
System.out.println(count); //输出结果
}
private static class Obj implements Comparable<Obj> { //创建一个价值类
int w, v;
double price;
public Obj(int w, int v) {
this.w = w;
this.v = v;
}
public double getPrice() {
this.price = v / w;
return price;
}
@Override
public int compareTo(Obj other) {
if (this.getPrice() > other.getPrice()) {
return 1;
} else if (this.getPrice() == other.getPrice()) {
return 0;
} else {
return -1;
}
}
}
<font size="6px">
七、乘船问题</font>
**题目描述：有n个人，第i个人重量为wi，每艘船的最大载重量均为C，且最多只能乘两人。用最少的船装下所有人。
贪心策略：考虑最轻的人i，如果每个人都无法和他一起坐船（重量和超过C），则唯一的方案就是每个人都坐一条船。否则，他应该选择能和他一起坐船的人中最重的一个人一起坐船
求需要船的数量**
思路分析：这道题首先要对每个人的重量进行排序，因为输入时不一定有序。然后初始化变量，并确定左指针和右指针。开始循环，如果如果最轻的人和最重的人的总重超过最大值，，就最重的人自己一条船，右指针左移一位。否则，最重的和最轻的一条船，左指针右移，右指针左移，两个人都上船。直到最后所有人都上船。输出结果。
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 cntOfBoat = 0; //所需船数
int p1 = 0; //左指针
int p2 = n - 1; //右指针
while (cntOfPerson > 0) { //出口条件，所有人上船
if (w[p1] + w[p2] > c) { //如果最轻的人和最重的人的总重超过最大值
p2--;
cntOfPerson--; //最重的人自己一条船，右指针左移一位
cntOfBoat++;
} else { //否则
p1++;
p2--; //最重的和最轻的一条船，左指针右移，右指针左移
cntOfPerson -= 2;
cntOfBoat++;
}
}
System.out.println(cntOfBoat); //输出总船数
}
