Lecture Notes for CS 512, Algorithm Design

12 April 2000, Greed

1. there are n items, with item i weighing w(i) pounds and costing c(i) dollars

2. the fractional knapsack problem involves filling a knapsack with the n items such that

   1. the sum of the weights of the items in the knapsack is no larger than W

   2. the sum of the costs of the items in the knapsack is as large as possible

   3. fractional items may appear in the knapsack

3. use brute force - generate all possible combinations of items that weigh no more than W and take the costliest combination - omega(2ⁿ)

4. this problem has optimal subproblems - removing item i from the knapsack must leave a maximal cost, otherwise the new sub-maximum would lead to a new maximum

5. the recursive algorithm has omega(2ⁿ) subproblems - dynamic programming won't help

6. work it in the other direction - remove the most valuable item

7. after taking as much as the most valuable as possible, fill the rest of the knapsack

8. greed

   1. optimal subproblems

   2. locally greedy (optimal) solutions lead to a globally optimal solution

      1. this has to be proved

         1. for the fractional knapsack problem, assume the knapsack items are ordered such that item 1 has the largest cost-weight ratio, item 2 has the next largest cost-weight ratio and so on.

         2. suppose an optimum solution S takes f₁ of item 1 for the knapsack

         3. let the greedy choice for item 1 be f'₁; then f'₁ >= f₁

         4. form solution S' by removing f'₁w(1) of items from S and replacing it with f'₁w(1) of item 1

         5. the solutions S' and S weigh the same, and, because item 1 has the highest cost-weight ratio among all items, the cost of item i in solution S' is at least as much as the cost of the items removed from solution(S). Solution S' is also optimal

         6. repeat with the next item chosen in the greedy method

9. the 0-1 knapsack problem - fractional items are not allowed

   1. the subproblems are optimal

   2. now greed is not optimal

   3. there are repeated subproblems - dynamic programming can solve this problem

10. scheduling
    given n items, item i starts at time s_i and finishes at time f_i, s_i <= f_i
    1. a consistent schedule is a subset of the n items with the property that, for any pair of items i != j in the subset, i and j don't overlap

    2. find the largest consistent schedule

    3. the algorithm

       1. sort the items by increasing finishing time

       2. pick the item with the earliest finishing time

       3. keep picking items with the earliest non-conflicting finishing time

       1. the optimal subproblem property holds

       2. the greedy-choice property holds too

          1. let S be an optimal schedule not containing the earliest f_i

          2. if activity j finishes first in S, form S' by removing j and adding i; S' and S have the same number of elements

          3. because S is a consistent schedule, for any activity k in S not equal to j, f_j <= s_k

          4. because f_i <= f_j, then S' is consistent too

          5. remove i from S' and j from S and repeat the argument with the next greedy choice

          6. the greedy choices lead to an optimal schedule, so the greedy-choice property holds.

This page last modified on 17 April 2000.