网站特色分析图怎么做,苏州网页制作服务商,小程序商城名字,嘉兴免费网站制作目录
活动选择问题
无重叠区间-Leetcode 435
分数背包问题--贪心解法
贪心法
0-1 背包问题
贪心法
贪心算法的局限
Set cover problem 活动选择问题
分析: /*
要在一个会议室举办n个活动
- 每个活动有它们各自的起始和结束时间
- 找出在时间上互不冲突的活动组合,能…目录
活动选择问题
无重叠区间-Leetcode 435
分数背包问题--贪心解法
贪心法
0-1 背包问题
贪心法
贪心算法的局限
Set cover problem 活动选择问题
分析: /*
要在一个会议室举办n个活动
- 每个活动有它们各自的起始和结束时间
- 找出在时间上互不冲突的活动组合,能够最充分利用会议室(举办的活动次数最多)例10 1 2 3 4 5 6 7 8 9|--------) |--------)|--------)选1 3 能够举办2个活动例20 1 2 3 4 5 6 7 8 9|---)|---)|-----------------------)|-------)|---)|---------------)4个活动几种贪心策略1.优先选择持续时间最短的活动 以下情形不满足方案out0 1 2 3 4 5 6 7 8 9|---------------)|-------)|----------------)\2.优先选择冲突最少的活动编号 0 1 2 3 4 5 6 7 8 91 |-------) 3 选中2 |-------) 43 |-------) 44 |-------) 45 |-------) 46 |-------) 2 选中7 |------------) 48 |--------) 49 |--------) 410 |--------) 411 |-------) 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;}Overridepublic 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) {ListActivityresult new ArrayList();Activity prev activities[0];result.add(prev);for(int i 1;ilength;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.length0){return 0;}Arrays.sort(intervals,Comparator.comparingInt(a-a[1]));int i,j;i0;int count 1;for(j 1;jintervals.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/82 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;}Overridepublic 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 黄金一块 4002 8 2400 红宝石戒指一枚 3003 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;}Overridepublic 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-FordPrim✔️Kruskal✔️零钱兑换❌动态规划Huffman 树✔️活动选择问题✔️分数背包问题✔️0-1 背包问题❌动态规划 Set cover problem
集合覆盖问题
这个问题后面会出文章! 敬请期待!
