目錄

活動(dòng)選擇問(wèn)題?

無(wú)重疊區(qū)間-Leetcode 435

分?jǐn)?shù)背包問(wèn)題--貪心解法

貪心法

0-1 背包問(wèn)題

貪心法

貪心算法的局限

Set cover problem

---

活動(dòng)選擇問(wèn)題?

分析:

/*
要在一個(gè)會(huì)議室舉辦n個(gè)活動(dòng)
- 每個(gè)活動(dòng)有它們各自的起始和結(jié)束時(shí)間
- 找出在時(shí)間上互不沖突的活動(dòng)組合,能夠最充分利用會(huì)議室(舉辦的活動(dòng)次數(shù)最多)例10   1   2   3   4   5   6   7   8   9|--------)              |--------)|--------)選1 3 能夠舉辦2個(gè)活動(dòng)例20   1   2   3   4   5   6   7   8   9|---)|---)|-----------------------)|-------)|---)|---------------)4個(gè)活動(dòng)幾種貪心策略1.優(yōu)先選擇持續(xù)時(shí)間最短的活動(dòng) 以下情形不滿足方案out0   1   2   3   4   5   6   7   8   9|---------------)|-------)|----------------)\2.優(yōu)先選擇沖突最少的活動(dòng)編號(hào) 0  1   2   3   4   5   6   7   8   91   |-------)                               3  選中2       |-------)                           43       |-------)                           44       |-------)                           45           |-------)                       46               |-------)                   2  選中7                   |------------)          48                            |--------)     49                            |--------)      410                           |--------)      411                               |-------)   3  選中但實(shí)際上應(yīng)該是1 5 7 11 所以這個(gè)也不行3. 優(yōu)先選擇最先開(kāi)始的活動(dòng) 不行0   1   2   3   4   5   6   7   8   9|-----------------------------------)|---)|---)|---)4. 優(yōu)先選擇最先結(jié)束的活動(dòng)*/

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;/*** <h1>活動(dòng)選擇問(wèn)題 - 貪心解法</h1>* Leetcode 435 無(wú)重疊區(qū)間本質(zhì)就是活動(dòng)選擇問(wèn)題*/
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) {List<Activity>result = new ArrayList<>();Activity prev = activities[0];result.add(prev);for(int i = 1;i<length;i++){Activity curr = activities[i]; //當(dāng)前正在處理的活動(dòng)if (curr.start >= prev.finish) {result.add(curr);prev = curr;}}for (Activity activity : result) {System.out.println(activity);}}
}

435. 無(wú)重疊區(qū)間 - 力扣（LeetCode）

無(wú)重疊區(qū)間-Leetcode 435

題目編號(hào)	題目標(biāo)題	算法思路
435	無(wú)重疊區(qū)間	貪心

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;}
}

• 找到不重疊的最多的活動(dòng)數(shù)（count），即活動(dòng)選擇問(wèn)題原始需求

• 在此基礎(chǔ)上，活動(dòng)總數(shù) - count，就是題目要的排除數(shù)量

分?jǐn)?shù)背包問(wèn)題--貪心解法

貪心法

/*
1. n個(gè)物品都是液體，有重量和價(jià)值
2. 現(xiàn)在你要取走 10升 的液體
3. 每次可以不拿，全拿，或拿一部分，問(wèn)最高價(jià)值是多少編號(hào) 重量(升) 價(jià)值0   4       24      水1   8       160     牛奶       選中 7/82   2       4000    五糧液     選中3   6       108     可樂(lè)4   1       4000    茅臺(tái)       選中8140簡(jiǎn)化起見(jiàn)，給出的數(shù)據(jù)都是【價(jià)值/重量】能夠整除，避免計(jì)算結(jié)果中出現(xiàn)小數(shù)，增加心算難度*/

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("最高價(jià)值為：" + max);}}

0-1 背包問(wèn)題

貪心法

可能得不到最優(yōu)解

 /*0-1 背包問(wèn)題1. n個(gè)物品都是固體，有重量和價(jià)值2. 現(xiàn)在你要取走不超過(guò) 10克 的物品3. 每次可以不拿或全拿，問(wèn)最高價(jià)值是多少編號(hào) 重量(g)  價(jià)值(元)0   1       1_000_000      鉆戒一枚        選中1   4       1600           黃金一塊        4002   8       2400           紅寶石戒指一枚   3003   5       30             白銀一塊按照分?jǐn)?shù)背包問(wèn)題解法: 1001630 但其實(shí)不對(duì)  應(yīng)該是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; // 最大價(jià)值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("最大價(jià)值是:" + max);}
}

貪心算法的局限

問(wèn)題名稱(chēng)	是否能用貪心得到最優(yōu)解	替換解法
Dijkstra(不存在負(fù)邊)	??
Dijkstra(存在負(fù)邊)	?	Bellman-Ford
Prim	??
Kruskal	??
零錢(qián)兌換	?	動(dòng)態(tài)規(guī)劃
Huffman 樹(shù)	??
活動(dòng)選擇問(wèn)題	??
分?jǐn)?shù)背包問(wèn)題	??
0-1 背包問(wèn)題	?	動(dòng)態(tài)規(guī)劃

Set cover problem

集合覆蓋問(wèn)題

這個(gè)問(wèn)題后面會(huì)出文章! 敬請(qǐng)期待!