贪心算法小总结--例题(活动安排问题，选择不相交区间，乘船问题，，背包问题)
程序员文章站
2022-06-03 14:38:38
...
目录
- 贪心法的概念
- 贪心法的性质
- 活动安排问题，选择不相交区间
- 乘船问题
- 背包问题
贪心法的概念
贪心算法是一种求解组合优化问题的算法设计技术，其求解过程由一系列决策构成每一步决策仅依赖于某种局部优化的性质。
和动态规划算法不同，贪心算法在做决策时候不必考虑所有子问题的选择结果。
贪心法的性质
- 贪心选择性质
- 最优子结构性质
贪心法的适用条件
问题的求解可以由一系列的决策步骤构成，每步决策依赖于某种局部最优的贪心策略。 保证每一步基于局部优化性质的选择最终导致全局的最优解。
主要设计步骤
- 将问题的求解看作是一系列的决策；
- 确定每一步决策所依据的局部优化性质；
- 证明每一步基于局部优化性质的选择最终导致全局最优解.
贪心法主要的难点在于证明其正确性，可以使用数学归纳法证明贪心法的正确性。
活动安排问题
题目链接
解题代码
import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;
/**
* 活动安排问题
* 题目链接 : http://acm.hdu.edu.cn/showproblem.php?pid=2037
*
*/
public class BestArrange { //提交时改成Main
//会议
public static class Program implements Comparable<Program>{
public int start; //开始时间
public int end; //结束时间
public Program(int start,int end){
this.start = start;
this.end = end;
}
@Override
public int compareTo(Program o) {
return this.end - o.end;//按照end升序
}
}
public static int bestArrange(Program[] programs,int n){
if(programs == null || n == 0)return 0;
Arrays.sort(programs,0,n); //按照end升序排列
int sum = 1; //第一个节目必看
int end = programs[0].end;
for(int i = 1; i < n; i++){
if(programs[i].start >= end){
sum ++;
end = programs[i].end;
}
}
return sum;
}
public static final int maxn = 10001;
public static void main(String[] args) {
Scanner cin = new Scanner(new BufferedInputStream(System.in));
while(cin.hasNext()){
int n = cin.nextInt();
if(n == 0)break;
Program[] programs = new Program[maxn];
for(int i = 0; i < n ; i++){
int s = cin.nextInt();
int e = cin.nextInt();
programs[i] = new Program(s,e);
}
System.out.println(bestArrange(programs,n));
}
}
}
选择不相交区间问题和活动安排问题的贪心思想是一样的，按照结束端点贪心选择即可。
乘船问题
题目描述
有n个人，第i个人重量为wi。每艘船的最大载重量均为C，且最多只能乘两个人。用最少的船装载所有人。
解析
首先从最轻的人开始考虑，那么他应该和最重的人去坐(贪心选择，为后面节省更多空间)，如果每个人都不能和它坐船，那么唯一的方法就是每个人做一艘船。
否则，他应该选择能够和他一起坐船的人中最重的那个，这样子才不会浪费。
反证法的两点证明：
- 假设i不与任何人同船,把j(或者比j轻的人)来同船会减少船的数量。
- 假设i与k同船，因为j是与i匹配的最重的，所以w(k)<=w(j)，则j加入其它船可能会使其它船超重，用的船数会变多；
import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;
public class Ship {
public static void main(String[] args) {
Scanner cin = new Scanner(new BufferedInputStream(System.in));
while(cin.hasNext()){
int C = cin.nextInt();
int n = cin.nextInt();
int[] w = new int[n+1];
for(int i = 0; i < n; i++) w[i] = cin.nextInt();
Arrays.sort(w,0,n); //排序的时候一定要指定范围，不然会得不到正确的结果
int i = 0, j = n-1;
int sum = 0;
while(i <= j){
if(i == j){//意味着其他的都已经配对了，只剩自己了
sum++;
break;
}
if(w[i] + w[j] <= C) {
sum++;
i++;
j--;
}else { //不能配对，让重的人做
sum++;
j--;
}
}
System.out.println(sum);
}
}
}
测试数据
测试数据:
85 6
5 84 85 80 84 83
90 3
90 45 60
100 5
50 50 90 40 60
输出:
5
3
3背包问题
背包问题和01背包问题不同，其差别在于每个物品可以放入一部分，这样的话，我们贪心选择单位重量价值依此从高到底的物品，最后一个物品能装多少就装多少
01背包问题用贪心算法得不到最优解的原因在于无法保证将背包装满，部分闲置的背包空间使得每千克背包空间的价值降低了。
import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;
/**
* 背包问题 注意不是01背包问题
*/
public class Kanpsack {
public static class Node implements Comparable<Node>{
public int w;
public int v;
public Node(int w, int v) {
this.w = w;
this.v = v;
}
//按照 v*1.0/w降序排列 单位
@Override
public int compareTo(Node o) {
return -(this.v*1.0/this.w < o.v*1.0/o.w ? -1 : (this.v*1.0/this.w == o.v*1.0/o.w ? 0: 1) );
}
}
public static void main(String[] args) {
Scanner cin = new Scanner(new BufferedInputStream(System.in));
int n = cin.nextInt();
int C = cin.nextInt();
Node[] node = new Node[n+1];
for(int i = 0; i < n; i++){
int w = cin.nextInt(); //不能直接写成node[i].w = cin.nextInt();
int v = cin.nextInt();
node[i] = new Node(w,v);
}
Arrays.sort(node,0,n);
double[] x = new double[n+1];
int now = C,i = 0;
for(; i < n; i++){
if(node[i].w > now)break;//装不下了
x[i] = 1; //装的下(装完整的一个)
now -= node[i].w;
}
if(i <= n-1){
x[i] = now*1.0/node[i].w; //最后一个能装多少是多少
}
for(i = 0; i < n; i++) System.out.print(x[i] + " " );
System.out.println();
}
}测试数据
3 50
10 60
20 100
30 120输出
1.000000 1.000000 0.666667