Divide and Conquer Greedy Algorithms HKOI分而治之的贪心算法hkoi.pptVIP

Divide and Conquer, Greedy Algorithms Joe Ng HKOI 2008 1–3-2008 Divide and Conquer 先分化，後征服 Problem solving technique Break down a problem into sub-problems Until they become simple easy to be solved directly Usually implemented by recursion Steps Divide: Break the problem into sub-problem Conquer: Solve the simple individual sub-problems Combine: Use the result of the sub-problems to construct the answer of the problem Example: Merge sort, Tower of Hanoi Example: Big Mod Repeated squaring Be careful of overflow problem Example: L-pieces 1003 L-pieces Length of the side must be in the form 2n What is the sub-problem? Solution Example: Diamond Chain To find the maximum interval sum Split the problem into sub-problems, until they are easy to solve Combine the sub-problem and construct the solution Divide and Conquer Try to divide the problem into sub-problems Be careful of the run-time Greedy Algorithm A greedy algorithm makes the choice looks best at that moment An optimal solution to the original problem contains optimal solutions to the sub-problems We can arrive the globally optimal solution by making a locally optimal choice, and then solving the sub-problems Example: Coins Suppose there are 7 kinds of coins $0.1, $0.2, $0.5, $1, $2, $5, $10 What is the minimum number of coins needed to pay $18 exactly? Is this strategy work for all kinds of combination of coins? Example: Fractional Knapsack There are N objects, each with weight wi and value vi. Any amount ( including fractions ) of each item can be taken provided that the total weight does not exceed W. How much of each item should we take in order to maximize the total value? Example: 0-1 Knapsack problem Similar to the fractional knapsack problem, but you can only choose to take the whole item or not. Greedy solvable? Example: Activities Can we solve this problem by greedy? How? By first start time? By shortest duration? By fewest overlap? By first end time? By ... Example: Diamond Chain Diamo