目录
活动选择问题
分析:
/*
要在一个会议室举办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);
}
}
}
无重叠区间-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
集合覆盖问题
这个问题后面会出文章! 敬请期待!