Greedy Method in Algorithm Design: An Overview
Greedy method is a powerful algorithm design technique where choices are made based on maximizing or minimizing an objective function. By making decisions greedily, one can reach either local or global optimal solutions step by step. While Greedy algorithm works efficiently in many scenarios, it may not always provide the optimal solution as demonstrated in problems involving note denominations.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Lecture 14 Greedy Method: Fractional Knapsack, Interval scheduling CS 161 Design and Analysis of Algorithms Ioannis Panageas
Greedy method The greedy method is a general algorithm design technique, in which given: configurations: different choices we need to make objective function: a score assigned to all configurations, which we want to either maximize or minimize We should make choices greedily: We can find a globally- optimal solution by a series of local improvements from a starting configuration. Design and Analysis of Algorithms
Greedy method The greedy method is a general algorithm design technique, in which given: configurations: different choices we need to make objective function: a score assigned to all configurations, which we want to either maximize or minimize We should make choices greedily: We can find a globally- optimal solution by a series of local improvements from a starting configuration. Example: Maxflow problem. Configurations: All possible flow functions. Objective function: Maximize flow value. Ford-Fulkerson makes choices greedily starting from flow ? = ?. Design and Analysis of Algorithms
Greedy does not always work Problem 1: Given a value ? and notes {1,2,5,10,20,50,100}, find the minimum number of notes to create value ?. You can use each note as many times as you want. Design and Analysis of Algorithms
Greedy does not always work Problem 1: Given a value ? and notes {1,2,5,10,20,50,100}, find the minimum number of notes to create value ?. You can use each note as many times as you want. Answer: Greedy approach works. Pick largest note that is at most ? and subtract from ?. Repeat until value becomes 0. E.g., for X=1477, you need fourteen 100s, one 50, one 20, one 5 and one 2. Design and Analysis of Algorithms
Greedy does not always work Problem 1: Given a value ? and notes {1,2,5,10,20,50,100}, find the minimum number of notes to create value ?. You can use each note as many times as you want. Answer: Greedy approach works. Pick largest note that is at most ? and subtract from ?. Repeat until value becomes 0. E.g., for X=1477, you need fourteen 100s, one 50, one 20, one 5 and one 2. Problem 2: Given a value ? and notes {1,2,7,10}, find the minimum number of notes to create value ?. You can use each note as many times as you want. Design and Analysis of Algorithms
Greedy does not always work Problem 1: Given a value ? and notes {1,2,5,10,20,50,100}, find the minimum number of notes to create value ?. You can use each note as many times as you want. Answer: Greedy approach works. Pick largest note that is at most ? and subtract from ?. Repeat until value becomes 0. E.g., for X=1477, you need fourteen 100s, one 50, one 20, one 5 and one 2. Problem 2: Given a value ? and notes {1,2,7,10}, find the minimum number of notes to create value ?. You can use each note as many times as you want. Answer: Greedy approach does not work as before. E.g., for X=14, you need two 7s, but greedy will give one 10, two 2s. Design and Analysis of Algorithms
Greedy does not always work Problem 1: Given a value ? and notes {1,2,5,10,20,50,100}, find the minimum number of notes to create value ?. You can use each note as many times as you want. Answer: Greedy approach works. Pick largest note that is at most ? and subtract from ?. Repeat until value becomes 0. E.g., for X=1477, you need fourteen 100s, one 50, one 20, one 5 and one 2. Problem 2: Given a value ? and notes {1,2,7,10}, find the minimum number of notes to create value ?. You can use each note as many times as you want. Answer: Greedy approach does not work as before. E.g., for X=14, you need two 7s, but greedy will give one 10, two 2s. Greedy does not work always Design and Analysis of Algorithms
Fractional Knapsack Problem: A set of ? items, with each item ? having positive weight ?? and positive value ??. You are asked to choose items with maximum total value so that the total weight is at most ?. We are allowed to take fractional amounts (some percentage of each item). Items: 1 2 3 4 5 Weight: 4 ml 8 ml 2 ml 6 ml 1 ml $12 $32 Value: knapsack with 10ml $40 $30 $50 $20 $3 $4 $5 $50 Value: ($ per ml) Design and Analysis of Algorithms
Fractional Knapsack Problem: A set of ? items, with each item ? having positive weight ?? and positive value ??. You are asked to choose items with maximum total value so that the total weight is at most ?. We are allowed to take fractional amounts (some percentage of each item). Solution: 1 ml of 5 2 ml of 3 6 ml of 4 1 ml of 2 Total Value: $124 Items: 1 2 3 4 5 Weight: 4 ml 8 ml 2 ml 6 ml 1 ml $12 $32 $40 knapsack with 10ml $30 $50 Value: Value: ($ per ml) $20 $3 $4 $5 $50 Design and Analysis of Algorithms
Fractional Knapsack Idea: Greedy approach. Keep taking item with highest value to weight ratio until knapsack is full or run out of items. Items: 1 2 3 4 5 Weight: 1 ml 4 ml 8 ml 2 ml 6 ml $12 $32 $40 $30 $50 Value: Value: ? = 10 ml ????? =$0 $20 $3 $4 $5 $50 Design and Analysis of Algorithms
Fractional Knapsack Idea: Greedy approach. Keep taking item with highest value to weight ratio until knapsack is full or run out of items. Items: 1 2 3 4 5 Weight: 6 ml 1 ml 4 ml 8 ml 2 ml $12 $32 $40 $30 $50 Value: Value: ? = 10 ml ????? =$0 $20 $3 $4 $5 $50 Design and Analysis of Algorithms
Fractional Knapsack Idea: Greedy approach. Keep taking item with highest value to weight ratio until knapsack is full or run out of items. Items: 1 2 3 4 Weight: 6 ml 4 ml 8 ml 2 ml $12 $32 $40 $30 Value: Value: ? = 9 ml ????? =$50 $20 $3 $4 $5 Design and Analysis of Algorithms
Fractional Knapsack Idea: Greedy approach. Keep taking item with highest value to weight ratio until knapsack is full or run out of items. Items: 1 2 3 4 Weight: 6 ml 4 ml 8 ml 2 ml $12 $32 $40 $30 Value: Value: ? = 9 ml ????? =$50 $20 $3 $4 $5 Design and Analysis of Algorithms
Fractional Knapsack Idea: Greedy approach. Keep taking item with highest value to weight ratio until knapsack is full or run out of items. Items: 1 2 4 Weight: 6 ml 4 ml 8 ml $12 $32 $30 Value: Value: ? = 7 ml ????? =$90 $3 $4 $5 Design and Analysis of Algorithms
Fractional Knapsack Idea: Greedy approach. Keep taking item with highest value to weight ratio until knapsack is full or run out of items. Items: 1 2 4 Weight: 6 ml 4 ml 8 ml $12 $32 $30 Value: Value: ? = 7 ml ????? =$90 $3 $4 $5 Design and Analysis of Algorithms
Fractional Knapsack Idea: Greedy approach. Keep taking item with highest value to weight ratio until knapsack is full or run out of items. Items: 1 2 Weight: 4 ml 8 ml $12 $32 Value: Value: ? = 1 ml ????? =$120 $3 $4 Design and Analysis of Algorithms
Fractional Knapsack Idea: Greedy approach. Keep taking item with highest value to weight ratio until knapsack is full or run out of items. Items: 1 2 Weight: 4 ml 8 ml $12 $32 Value: Value: ? = 1 ml ????? =$120 $3 $4 Design and Analysis of Algorithms
Fractional Knapsack Idea: Greedy approach. Keep taking item with highest value to weight ratio until knapsack is full or run out of items. Items: 1 2 Weight: 4 ml 7 ml $12 $32 Value: Value: ? = 0 ml ????? =$124 $3 $4 Running time: ? Design and Analysis of Algorithms
Fractional Knapsack Idea: Greedy approach. Keep taking item with highest value to weight ratio until knapsack is full or run out of items. Items: 1 2 Weight: 4 ml 7 ml $12 $32 Value: Value: ? = 0 ml ????? =$124 $3 $4 Running time: If we sort the items with respect to value to weight ratio then (? log?). Design and Analysis of Algorithms
Fractional Knapsack Pseudocode: Design and Analysis of Algorithms
Fractional Knapsack Pseudocode: Compute the ratios Initialization While knapsack not full If whole item fits Design and Analysis of Algorithms
Fractional Knapsack Percentage of item i that fits Pseudocode: Compute the ratios Initialization While knapsack not full If whole item fits Design and Analysis of Algorithms
Fractional Knapsack Pseudocode: This is fast, in ?(?) time. Design and Analysis of Algorithms
Fractional Knapsack Why greedy works: General argument. Suppose there is a better solution. Assume items are order in decreasing order of value per weight, i.e., ?1 ?2 ??. Let ?1, ,?? be the weight values of the items in the knapsack for the better solution. Design and Analysis of Algorithms
Fractional Knapsack Why greedy works: General argument. Suppose there is a better solution. Assume items are order in decreasing order of value per weight, i.e., ?1 ?2 ??. Let ?1, ,?? be the weight values of the items in the knapsack for the better solution. Since it is different from what greedy returns, there must be indices ?,? so that ??> ?? and ??> 0 and ??< ??. Design and Analysis of Algorithms
Fractional Knapsack Why greedy works: General argument. Suppose there is a better solution. Assume items are order in decreasing order of value per weight, i.e., ?1 ?2 ??. Let ?1, ,?? be the weight values of the items in the knapsack for the better solution. Since it is different from what greedy returns, there must be indices ?,? so that ??> ?? and ??> 0 and ??< ??. value per weight of item ? is larger than ? Design and Analysis of Algorithms
Fractional Knapsack Why greedy works: General argument. Suppose there is a better solution. Assume items are order in decreasing order of value per weight, i.e., ?1 ?2 ??. Let ?1, ,?? be the weight values of the items in the knapsack for the better solution. Since it is different from what greedy returns, there must be indices ?,? so that ??> ?? and ??> 0 and ??< ??. value per weight of item ? is larger than ? Part or all of item ? is in the knapsack Design and Analysis of Algorithms
Fractional Knapsack Why greedy works: General argument. Suppose there is a better solution. Assume items are order in decreasing order of value per weight, i.e., ?1 ?2 ??. Let ?1, ,?? be the weight values of the items in the knapsack for the better solution. Since it is different from what greedy returns, there must be indices ?,? so that ??> ?? and ??> 0 and ??< ??. value per weight of item ? is larger than ? Part or all of item ? is in the knapsack Not all of item ? is in the knapsack Design and Analysis of Algorithms
Fractional Knapsack Why greedy works: General argument. Suppose there is a better solution. Assume items are order in decreasing order of value per weight, i.e., ?1 ?2 ??. Let ?1, ,?? be the weight values of the items in the knapsack for the better solution. Since it is different from what greedy returns, there must be indices ?,? so that ??> ?? and ??> 0 and ??< ??. Exchange part of item ?, with part of item ?. How much? Say the minimum of ?? ?? ??? ??. Design and Analysis of Algorithms
Fractional Knapsack Why greedy works: General argument. Suppose there is a better solution. Assume items are order in decreasing order of value per weight, i.e., ?1 ?2 ??. Let ?1, ,?? be the weight values of the items in the knapsack for the better solution. Since it is different from what greedy returns, there must be indices ?,? so that ??> ?? and ??> 0 and ??< ??. Exchange part of item ?, with part of item ?. How much? Say the minimum of ?? ?? ??? ??. Total value will increase by ?? ?? min(?? ??,??) Design and Analysis of Algorithms
Task scheduling Problem: Given: a set ? of ? tasks, each having a start time ??and a finish time ?? (where ??< ??) Goal: Perform all the tasks using a minimum number of machines. A machine can serve one task at a given time. Design and Analysis of Algorithms
Task scheduling Problem: Given: a set ? of ? tasks, each having a start time ??and a finish time ?? (where ??< ??) Goal: Perform all the tasks using a minimum number of machines. A machine can serve one task at a given time. Machine 3 Machine 2 Machine 1 1 2 3 4 5 6 7 8 9 Design and Analysis of Algorithms
Task scheduling Idea: Greedy approach. Consider tasks in increasing order of their start time. Assign first task to machine 1 and set ? = 1. When considering a new task, if all machines are busy, create a new machine, set ? = ? + 1 and assign the new task to the new machine otherwise assign the new task to an available machine. Design and Analysis of Algorithms
Task scheduling Idea: Greedy approach. Consider tasks in increasing order of their start time. Assign first task to machine 1 and set ? = 1. When considering a new task, if all machines are busy, create a new machine, set ? = ? + 1 and assign the new task to the new machine otherwise assign the new task to an available machine. Design and Analysis of Algorithms
Task scheduling Idea: Greedy approach. Consider tasks in increasing order of their start time. Assign first task to machine 1 and set ? = 1. When considering a new task, if all machines are busy, create a new machine, set ? = ? + 1 and assign the new task to the new machine otherwise assign the new task to an available machine. Design and Analysis of Algorithms
Task scheduling Idea: Greedy approach. Consider tasks in increasing order of their start time. Assign first task to machine 1 and set ? = 1. When considering a new task, if all machines are busy, create a new machine, set ? = ? + 1 and assign the new task to the new machine otherwise assign the new task to an available machine. Design and Analysis of Algorithms
Task scheduling Idea: Greedy approach. Consider tasks in increasing order of their start time. Assign first task to machine 1 and set ? = 1. When considering a new task, if all machines are busy, create a new machine, set ? = ? + 1 and assign the new task to the new machine otherwise assign the new task to an available machine. Design and Analysis of Algorithms
Task scheduling Idea: Greedy approach. Consider tasks in increasing order of their start time. Assign first task to machine 1 and set ? = 1. When considering a new task, if all machines are busy, create a new machine, set ? = ? + 1 and assign the new task to the new machine otherwise assign the new task to an available machine. Design and Analysis of Algorithms
Task scheduling Idea: Greedy approach. Consider tasks in increasing order of their start time. Assign first task to machine 1 and set ? = 1. When considering a new task, if all machines are busy, create a new machine, set ? = ? + 1 and assign the new task to the new machine otherwise assign the new task to an available machine. Design and Analysis of Algorithms
Task scheduling Idea: Greedy approach. Consider tasks in increasing order of their start time. Assign first task to machine 1 and set ? = 1. When considering a new task, if all machines are busy, create a new machine, set ? = ? + 1 and assign the new task to the new machine otherwise assign the new task to an available machine. Design and Analysis of Algorithms
Task scheduling Idea: Greedy approach. Consider tasks in increasing order of their start time. Assign first task to machine 1 and set ? = 1. When considering a new task, if all machines are busy, create a new machine, set ? = ? + 1 and assign the new task to the new machine otherwise assign the new task to an available machine. Why greedy works: General argument. Suppose there is a better solution, using ? 1 machines instead of ?. Design and Analysis of Algorithms
Task scheduling Idea: Greedy approach. Consider tasks in increasing order of their start time. Assign first task to machine 1 and set ? = 1. When considering a new task, if all machines are busy, create a new machine, set ? = ? + 1 and assign the new task to the new machine otherwise assign the new task to an available machine. Why greedy works: General argument. Suppose there is a better solution, using ? 1 machines instead of ?. Let ? be the first task that used Machine ?. At that moment, there are must be ? 1 conflicting tasks with task ?. Design and Analysis of Algorithms
Task scheduling Idea: Greedy approach. Consider tasks in increasing order of their start time. Assign first task to machine 1 and set ? = 1. When considering a new task, if all machines are busy, create a new machine, set ? = ? + 1 and assign the new task to the new machine otherwise assign the new task to an available machine. Why greedy works: General argument. Suppose there is a better solution, using ? 1 machines instead of ?. Let ? be the first task that used Machine ?. At that moment, there are must be ? 1 conflicting tasks with task ?. All these ? 1 tasks have finishing times larger than ?? and starting times less than or equal to ??. Design and Analysis of Algorithms
Task scheduling Idea: Greedy approach. Consider tasks in increasing order of their start time. Assign first task to machine 1 and set ? = 1. When considering a new task, if all machines are busy, create a new machine, set ? = ? + 1 and assign the new task to the new machine otherwise assign the new task to an available machine. Why greedy works: General argument. Suppose there is a better solution, using ? 1 machines instead of ?. Let ? be the first task that used Machine ?. At that moment, there are must be ? 1 conflicting tasks with task ?. All these ? 1 tasks have finishing times larger than ?? and starting times less than or equal to ??. These tasks are conflict with each other! So we have ? tasks that conflict with each other, we need k machines! Design and Analysis of Algorithms
Task scheduling Idea: Greedy approach. Consider tasks in increasing order of their start time. Assign first task to machine 1 and set ? = 1. When considering a new task, if all machines are busy, create a new machine, set ? = ? + 1 and assign the new task to the new machine otherwise assign the new task to an available machine. Why greedy works: General argument. Suppose there is a better solution, using ? 1 machines instead of ?. Let ? be the first task that used Machine ?. At that moment, there are must be ? 1 conflicting tasks with task ?. All these ? 1 tasks have finishing times larger than ?? and starting times less than or equal to ??. These tasks are conflict with each other! So we have ? tasks that conflict with each other, we need k machines! Contradiction! Design and Analysis of Algorithms
