1.基本概述
贪心算法是一种解决优化问题的算法范例，其基本思想是每一步都选择当前状态下的最优解，希望通过局部最优的选择最终得到全局最优解。
比如Dijkstra（选取当前距离最小的顶点）、Prim（选取当前距离最小的顶点）、Kruskal（选取当前距离最短的边）。
因为没有考虑所有可能，局部最优的堆叠不一定让最终解最优，比如Dijkstra算法处理负环的时候。
Bellman-Ford并没有考虑局部距离最小的顶点，而是每次都处理所有边，所以不是贪心算法，当然效率不如 Dijkstra。
2.活动选择问题
要在一个会议室举办 n 个活动
每个活动有它们各自的起始和结束时间
找出在时间上互不冲突的活动组合，能够最充分利用会议室（举办的活动次数最多）
优先选择最先结束的活动
package com.dreams;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
/**
* 活动选择问题 - 贪心解法
* Leetcode 435 无重叠区间本质就是活动选择问题
*/
public class ActivitySelectionProblem {
/*
要在一个会议室举办 n 个活动
- 每个活动有它们各自的起始和结束时间
- 找出在时间上互不冲突的活动组合，能够最充分利用会议室（举办的活动次数最多）
4. 优先选择最先结束的活动
*/
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)
};
Arrays.sort(activities, Comparator.comparingInt(Activity::getFinish));
System.out.println(Arrays.toString(activities));
System.out.println(select(activities));
}
public static int select(Activity[] activities) {
Arrays.sort(activities, Comparator.comparingInt(Activity::getFinish));
List<Activity> result = new ArrayList<>();
Activity prev = activities[0]; // 上次被选中的活动
result.add(prev);
for (int i = 1; i < activities.length; i++) {
Activity curr = activities[i]; // 正在处理的活动
if (curr.start >= prev.finish) {
result.add(curr);
prev = curr;
}
}
return activities.length - result.size();
}
}
3.分数背包问题
1. n个物品都是液体，有重量和价值
2. 现在你要取走 10升 的液体
3. 每次可以不拿，全拿，或拿一部分，问最高价值是多少
编号 重量(升) 价值
0 4 24 水
1 8 160 牛奶 选中 7/8
2 2 4000 五粮液 选中
3 6 108 可乐
4 1 4000 茅台 选中
简化起见，给出的数据都是【价值/重量】能够整除，避免计算结果中出现小数，增加心算难度。
分数背包问题：
- 首先，对物品数组按照单位价值（价值/重量）从大到小排序。
- 然后，遍历排序后的物品数组，如果当前物品的重量小于等于背包剩余容量，则将该物品全部拿走，更新背包剩余容量和已获得的最大价值；否则，根据当前物品的单位价值拿走部分物品，更新最大价值，并退出循环。
package com.dreams;
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 unitValue() {
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::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);
}
}
4.零钱兑换II
通过递归方法解决零钱兑换问题的算法。这种方法通过穷举所有可能的组合来计算凑成总金额的方式数：
package com.dreams.dynamicprogramming;
/**
* 零钱兑换 II - 穷举解法
* 凑成总金额有几种凑法？
*/
public class Leetcode518 {
public int change(int[] coins, int amount) {
return rec(0, coins, amount);
}
/**
* 求凑成剩余金额的解的个数
*
* @param index 当前硬币索引
* @param coins 硬币面值数组
* @param remainder 剩余金额
* @return 解的个数
*/
public int rec(int index, int[] coins, int remainder) {
// 情况1：剩余金额 < 0 - 无解
int count = 0;
if (remainder < 0) {
return 0;
}
// 情况2：剩余金额 == 0 - 有解
else if (remainder == 0) {
return 1;
}
// 情况3：剩余金额 > 0 - 继续递归
else {
for (int i = index; i < coins.length; i++) {
count += rec(i, coins, remainder - coins[i]);
}
}
return count;
}
public static void main(String[] args) {
Leetcode518 leetcode = new Leetcode518();
int count = leetcode.change(new int[]{1, 2, 5}, 5);
System.out.println(count);
}
}递归过程：
由小到大递归过程
rec(1,5)
rec(1,4)
| rec(1,3)
| | rec(1,2)
| | | rec(1,1)
| | | | rec(1,0)
| | | | rec(2,-1)
| | | | rec(5,-4)
| | | rec(2,0)
| | | rec(5,-3)
| | rec(2,1)
| | | rec(2,-1)
| | | rec(5,-4)
| | rec(5,-2)
| rec(2,2)
| | rec(2,0)
| | rec(5,-3)
| rec(5,-1)
rec(2,3)
| rec(2,1)
| | rec(2,-1)
| | rec(5,-4)
| rec(5,-2)
rec(5,0)
由大到小递归过程
rec(5,5)
rec(5,0)
rec(2,3)
| rec(2,1)
| | rec(2,-1)
| | rec(1,0)
| rec(1,2)
| | rec(1,1)
| | | rec(1,0)
rec(1,4)
| rec(1,3)
| | rec(1,2)
| | | rec(1,1)
| | | | rec(1,0)
顺序优化（从大到小传递，可以减少递归次数）：
int count = leetcode.change(new int[]{5, 2, 1}, 5);使用贪心算法可能出现错误答案，这里使用动态规划。
package com.dreams;
public class Leetcode518 {
public int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int coin : coins) {
for (int i = coin; i <= amount; i++) {
dp[i] += dp[i - coin];
}
}
return dp[amount];
}
public static void main(String[] args) {
Leetcode518 leetcode = new Leetcode518();
int count = leetcode.change(5, new int[]{1, 2, 5});
System.out.println(count);
}
}
5.0-1背包问题
同样可能无法达到最优解，而需要使用动态规划。
参考
