1.204 Lecture 10 Greedy algorithms: K k( it lb d ti ) Knapsack (capital budgeting) Job scheduling Greedy method • Local impprovement method – Does not look at problem globally – Takes best immediate step to find a solution – Useful in many cases where • Objectives or constraints are uncertain, or • An approximate answer is all that’s required – Generally O(n) complexity, easy to implement and interpret results • Often requires sorting the data first, which is O(n lg n) – In some cases, greedy algorithms provide optimal solutions(shortest paths, spanning trees, some job schedulingproblems) • In most cases they are approximate algorithms • Sometimes used as a part of an exact algorithm (e.g., as a relaxation in an integer programming algorithm) 12General greedy algorithm// Pseudocodepublic solution greedy(problem) {solution= empty set;problem.sort(); // Usually place elements in orderfor (element: problem) {if (element feasible and appears optimal)solution= union(solution, element);return solution;}Some greedy algorithms sort, some use a heap, some don’t need to sort at all.Greedy knapsack problemWe have n objects, each with weight wi and profit pi .The knapsack has capacity MMxwtsxpinii≤∑∑<≤..max0The knapsack has capacity M.niwpxMxwiiiinii<≤≥≥<=≤≤∑<≤0,0,0100Greedy knapsack algorithm Algorithm chooses element with highest value/weight ratio first, the next highest second, and so on until it reaches the capacity of the knapsack. This is the same as a gradient or derivative method. Knapsack: integer or not? Let M= 1. Integer solution is {2, 3}, an unexpected result in some contexts. Greedy solution is {1, 98% of 2}. If problem has hard constraints, need integer solution. If constraints are fuzzy, greedy solution may be better. 3Knapsack problems • Truck packing: integer knapsack – Packing problem in 2 and 3 dimensions is extension Packing problem in 2 and 3 dimensions is extension • Investment program: – Greedy knapsack at high level – Can be integer knapsack at individual transaction level – (Highway investment or telecom capital investment programs often handled as integer problem, with occasionally hard-to-interpret results) – Used to train telecom execs for spectrum auction • Interactions between projects: – Greedy can be extended to handle interactions between small numbers of projects (that can be enumerated) – Integer program handles this explicitly Greedy knapsack code, p.1 public class Knapsack { private static class Item implements Comparable { public double ratio; // Profit/weight ratio public int weight; public Item(double r, int w) { ratio = r; weight = w; } public int compareTo(Object o) { Item other = (Item) o; if (ratio > other ratio) if (ratio > other.ratio) // Descending sort // Descending sort return -1; else if (ratio < other.ratio) return 1; else return 0; } } 4tGreedy knapsack code, p.2 public static double[] knapsack(Item[] e, int m) { int upper = m; // Knapsack capacity // 0-1 answer array: 1 if item in knapsack 0 if not // 0-1 answer array: 1 if item in knapsack, 0 if not double[] x= new double[e.length]; int i; for (i= 0; i < e.length; i++) { if (e[i].weight > upper) break; x[i]= 1.0; upper -= e[i].weight; }} if (i < e.length) // If all items not in knapsack x[i]= (double) upper/ e[i].weight; // Fractional item return x; } Greedy knapsack code, p.3 public static void main(String[] args) { Item a = new Item(2.0, 2); Item b = new Item((1.5,, 4);); Item c = new Item(2.5, 2); Item d = new Item(1.66667, 3); Item[] e = { a, b, c, d }; Arrays.sort(e); int m = 7; System.out.println("Capacity: " + m); double[] projectSet= knapsack(e, m); double cumProfit= 0.0; f (i t i 0 i l h i ) { for (int i= 0; i < e.length; i++) { System.out.println( … ); // See Java code cumProfit+= projectSet[i]*e[i].weight*e[i].ratio; } System.out.println("Cumulative benefit: " + cumProfit); } 5Greedy knapsack output Capacity: 7 i: ratio: 2.5 wgt: 2 profit: 5.0 in? 1.0 i: ratio: 2.0 wgt: 2 profit: 4.0 in? 1.0 i: ratio: 1.67 wgt: 3 profit: 5.0 in? 1.0 i: ratio: 1.5 wgt: 4 profit: 6.0 in? 0.0 Cumulative benefit: 14.0 (Roundoff errors omitted) This greedy example yields an integer solution. Most don’t: Run knapsack() with m= 6 or 8 or … Greedy job scheduling • We have a set of n jobs to run on a processor (CPU) or machine • Each job i has a deadline di >=1 and profit pi >=0 • There is one processor or machine • Each job takes 1 unit of time (simplification) • We earn the profit if and only if the job is completed by its deadline – “Profit” can be the priority of the task in a real time system that discards tasks that cannot be completed by their deadline • We want to find the subset of jobs that maximizes our profit • This is a restricted version of a general job scheduling problem, which is an integer programming problem – Example use in telecom engineering and construction scheduling – Many small jobs, “profit” proportional to customers served – This is then combined with integer programming solution for big jobs • Greedy also used in how many machines/people problems (hw 1) – Buy versus contract 6Greedy job scheduling example Number of jobs n=5. Time slots 1, 2, 3. (Slot 0 is sentinel)j ( ) Job (i) Profit Deadline Profit/Time A 100 2 100 B 19 1 19 C 27 2 27 D 25 1 25 EE 1515 33 1515 Greedy job scheduling algorithm • Sort jobs by profit/time ratio (slope or derivative): – A (deadline 2), C (2), D (1), B (1), E (3)A (deadline 2), C (2), D (1), B (1), E (3) • Place each job at latest time that meets its deadline – Nothing is gained by scheduling it earlier, and scheduling it earlier could prevent another more profitable job from being done – Solution is {C, A, E} with profit of 142 C (27)() A (100) E (15) 0 1 2 3 Time D, B infeasible – This can be subproblem: how many machines/people needed 7Greedy job data structure • Simple greedy job algorithm spends much timeSimple greedy job algorithm spends much time looking for latest slot a job can use, especially as algorithm progresses and many slots are filled. – n jobs would, on average, search n/2 slots – This would be an O(n2) algorithm • By using our set data structure, it becomes nearly O(n)nearly O(n) – Recall set find and union are O(Ackermann’s function), which is nearly O(1) – We invoke n set finds and unions in our greedy