贪心算法-活动选择问题&背包问题

目录

活动选择问题 

无重叠区间-Leetcode 435

分数背包问题--贪心解法

贪心法

0-1 背包问题

贪心法

贪心算法的局限

Set cover problem


活动选择问题 

分析:

/*
要在一个会议室举办n个活动
- 每个活动有它们各自的起始和结束时间
- 找出在时间上互不冲突的活动组合,能够最充分利用会议室(举办的活动次数最多)

例1
    0   1   2   3   4   5   6   7   8   9
        |--------)              
            |--------)
                 |--------)

 选1 3 能够举办2个活动

例2
    0   1   2   3   4   5   6   7   8   9
        |---)
                |---)
    |-----------------------)
                        |-------)
                                    |---)
                        |---------------)

  4个活动


  几种贪心策略
  1.优先选择持续时间最短的活动 以下情形不满足方案out
        0   1   2   3   4   5   6   7   8   9
            |---------------)
                        |-------)
                            |----------------)\
  2.优先选择冲突最少的活动
  编号 0  1   2   3   4   5   6   7   8   9
  1   |-------)                               3  选中
  2       |-------)                           4
  3       |-------)                           4
  4       |-------)                           4
  5           |-------)                       4
  6               |-------)                   2  选中
  7                   |------------)          4
  8                            |--------)     4
  9                            |--------)      4
  10                           |--------)      4
  11                               |-------)   3  选中

    但实际上应该是1 5 7 11 所以这个也不行

    3. 优先选择最先开始的活动 不行
        0   1   2   3   4   5   6   7   8   9
        |-----------------------------------)
            |---)
                |---)
                    |---)

    4. 优先选择最先结束的活动

 */
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * <h1>活动选择问题 - 贪心解法</h1>
 * Leetcode 435 无重叠区间本质就是活动选择问题
 */
public class ActivitySelectionProblem {
    static class Activity{
        int index;
        int start;
        int finish;

        public Activity(int index,int start,int finish){
            this.index = index;
            this.start = start;
            this.finish = finish;
        }
        public int getFinish(){
            return finish;
        }

        @Override
        public String toString(){
            return "Activity("+index+")";
        }
    }

    public static void main(String[] args) {
        Activity[] activities = new Activity[]{
                new Activity(0, 1, 3),
                new Activity(1, 2, 4),
                new Activity(2, 3, 5)
        };
//        Activity[] activities = new Activity[]{
//                new Activity(0, 1, 2),
//                new Activity(1, 3, 4),
//                new Activity(2, 0, 6),
//                new Activity(3, 5, 7),
//                new Activity(4, 8, 9),
//                new Activity(5, 5, 9)
//        };
        Arrays.sort(activities, Comparator.comparingInt(Activity::getFinish));
        System.out.println(Arrays.toString(activities));
        select(activities, activities.length);
    }

    public static void select(Activity[] activities, int length) {
        List<Activity>result = new ArrayList<>();
        Activity prev = activities[0];
        result.add(prev);
        for(int i = 1;i<length;i++){
            Activity curr = activities[i]; //当前正在处理的活动
            if (curr.start >= prev.finish) {
                result.add(curr);
                prev = curr;
            }
        }
        for (Activity activity : result) {
            System.out.println(activity);
        }
    }
}

435. 无重叠区间 - 力扣(LeetCode)

无重叠区间-Leetcode 435
题目编号 题目标题 算法思路
435 无重叠区间 贪心
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if(intervals.length==0){
            return 0;
        }
        Arrays.sort(intervals,Comparator.comparingInt(a->a[1]));
        int i,j;
        i=0;
        int count =1;
        for(j = 1;j<intervals.length;j++){
            if(intervals[j][0] >= intervals[i][1]){
                i = j;
                count++;
            }
        }
        return intervals.length-count;
    }
}

  • 找到不重叠的最多的活动数(count),即活动选择问题原始需求

  • 在此基础上,活动总数 - count,就是题目要的排除数量

分数背包问题--贪心解法

贪心法
/*
1. n个物品都是液体,有重量和价值
2. 现在你要取走 10升 的液体
3. 每次可以不拿,全拿,或拿一部分,问最高价值是多少

    编号 重量(升) 价值
    0   4       24      水
    1   8       160     牛奶       选中 7/8
    2   2       4000    五粮液     选中
    3   6       108     可乐
    4   1       4000    茅台       选中

    8140

    简化起见,给出的数据都是【价值/重量】能够整除,避免计算结果中出现小数,增加心算难度
 */
import java.util.Arrays;
import java.util.Comparator;

public class FractionalKnapsackProblem {

    static class Item {
        int index;
        int weight;
        int value;

        public Item(int index, int weight, int value) {
            this.index = index;
            this.weight = weight;
            this.value = value;
        }

        public int unitPrice() {
            return value / weight;
        }

        @Override
        public String toString() {
            return "Item(" + index + ")";
        }
    }

    public static void main(String[] args) {
        Item[] items = new Item[]{
                new Item(0, 4, 24),
                new Item(1, 8, 160),
                new Item(2, 2, 4000),
                new Item(3, 6, 108),
                new Item(4, 1, 4000),
        };
        select(items, 10);
    }

    static void select(Item[] items, int total) {
        Arrays.sort(items, Comparator.comparingInt(Item::unitPrice).reversed());
        //reversed()降序
        int remainder = total;
        int max = 0;
        for (Item item : items) {
            if (remainder - item.weight >= 0) {//一次能够拿完
                max += item.value;
                remainder -= item.weight;
            } else {//拿不完
                max += remainder * item.unitPrice();
                break;
            }
        }
        System.out.println("最高价值为:" + max);
    }


}

0-1 背包问题

贪心法

可能得不到最优解

 /*
    0-1 背包问题

    1. n个物品都是固体,有重量和价值
    2. 现在你要取走不超过 10克 的物品
    3. 每次可以不拿或全拿,问最高价值是多少

        编号 重量(g)  价值(元)
        0   1       1_000_000      钻戒一枚        选中
        1   4       1600           黄金一块        400
        2   8       2400           红宝石戒指一枚   300
        3   5       30             白银一块

按照分数背包问题解法: 1001630 但其实不对  应该是1002400
     */
import java.util.Arrays;
import java.util.Comparator;

public class KnapsackProblem {
   

    static class Item {
        int index;
        int weight;
        int value;

        public Item(int index, int weight, int value) {
            this.index = index;
            this.weight = weight;
            this.value = value;
        }

        public int unitValue() {
            return value / weight;
        }

        @Override
        public String toString() {
            return "Item(" + index + ")";
        }
    }

    public static void main(String[] args) {
        Item[] items = new Item[]{
                new Item(0, 1, 1_000_000),
                new Item(1, 4, 1600),
                new Item(2, 8, 2400),
                new Item(3, 5, 30)
        };
        select(items, 10);
    }

    static void select(Item[] items, int total) {
        Arrays.sort(items, Comparator.comparingInt(Item::unitValue).reversed());
        int max = 0; // 最大价值
        for (Item item : items) {
            System.out.println(item);
            if (total >= item.weight) { // 可以拿完
                total -= item.weight;
                max += item.value;
            } else { // 拿不完
//                max += total * item.unitValue();
//                break;
            }
        }
        System.out.println("最大价值是:" + max);
    }
}

贪心算法的局限

问题名称 是否能用贪心得到最优解 替换解法
Dijkstra(不存在负边) ✔️
Dijkstra(存在负边) Bellman-Ford
Prim ✔️
Kruskal ✔️
零钱兑换 动态规划
Huffman 树 ✔️
活动选择问题 ✔️
分数背包问题 ✔️
0-1 背包问题 动态规划

Set cover problem

集合覆盖问题

这个问题后面会出文章! 敬请期待!

上一篇:macos如何安装Tesseract软件and常规应用及问题处理


下一篇:文件传送协议-贰、简单文件传输协议TFTP